Okruzno takmichenje

[EclipsE]

Danas je bilo okruzno takmichenje iz programiranja odrzano u ETS "Rade Konchar". Evo par zadataka, i par problema koje mozete da reshavate da vam ne bude dosadno :P

Problem 1. Najslabija karika

U popularnom televizijskom kvizu "Najslabija karika" nekoliko takmicara redom u krug odgovaraju na postavljena pitanja. Prvi tacan odgovor donosi jedan dinar, dok svaki sledeci tacan odgovor u nizu donosi duplo vishe poena nego prethodni. Kada neko odgovori netacno - lanac se prekida i sledeci tacan odgovor donosi 1 dinar. Kada takmicar kzaze "Banka", sav novac u trenutnom lancu tacnih odgovora se dodaje na ukupnu zagarantovanu sumu, a naredni tacan odgovor ponovo vredi 1 dinar. Ako takmicari u nizu daju 15 tachnih odgovora, a da izmedju nije bilo bankiranja - nagrada iznosi neverovatnih 1000000000 (milijardu) dinara, bez obzira da li je neko rekao "Banka" ili su pre toga takmichari osvojili neshto novca. Vama su na raspolaganju podaci iz prethodne emisije. Treba odrediti koliko dinara su takmichari zaradili.

Ulaz. (Ulazni podaci se nalaze u datoteci karika.in) U prvom redu ulazne datoteke se nalazi niz znakova. Svaki od znakova je iz skupa {'O', 'X', 'B'}. (sva tri moguca znaka su velika slova, shto znachi da prvi od tri znaka nije cifra nula, vec slovo O) i oni predstavljaju tacan odgovor, netacan odgovor i banku. Duzina niza znakova je manja ili jednaka 100000.

Izlaz. (Izlazne podatke upisati u datoteku karika.out) U izlaznu datoteku treba upisati broj dinara koji su takmi chari zaradili.

Primer 1.
karika.in
OOOBXOXBXOOBOX

karika.out
10

Objasnjenje. Posle bankiranja, takmichari redovno dobijaju 7 + 0 + 3 = 10 dinara

Primer 2.
karika.in
XOOBOOOOOOOOOOOOOOOOXOOB

karika.out
1000000000

Objasnjenje. Takmichari imaju niz od 15 tachnih odgovora, pa zaradjuju 1000000000 dinara.

[EclipsE]

Problem 2. Igra

Na papiru je napisan broj N (1 <= N <= 10^7). Dva igracha naizmenichno rade sledece: igrach koji je na potezu bira neki delilac broja koji je napisan na papiru (delilac ne sme biti 1 ili broj sa papira), racuna kolichnik broja sa papira i izabranog delioca, brise broj koji se nalazi na papriu, i pishe dobijeni kolichnik. Ukoliko igrach ne moze da odigra svoj potez (tj. jedini delioci su 1 i broj sa papira), on je pobednik. Napisati program koji treba da uchita niz brojeva i za svaki od tih brojeva odredi koji igrach pobedjuje u partiji na chijem pochetku se na papiru nalazi taj broj. Smatrati da oba igracha igraju optimalno (povlache najbolje poteze).

Ulaz. (Ulazni podaci se nalaze u datoteci igra.in) U prvom redu ulazne datoteke se nalazi broj M(5 <= M <= 20). U narednih M redova nalazi se po jedan broj N (1 <= N <= 10^7).

Izlaz. (Izlazne podatke upisati u datoteku igra.out) U izlaznu datoteku treba upisati M redova. U i-tom redu ispisati broj 1, ako prvi igrach pobedjuje kad je pochetni broj na papiru Ni, a 2, ako drugi igrach pobedjuje.

Primer 1.
igra.in
5
1
4
5
10
25

igra.out
1
2
1
2
2

[Stevvan]

Kako si uradio? E onaj ko ovo uradi neka ne postavlja odmah resenje, sem ako drugi nece, kako bi svi mogli prvo da pokusaju da urade

[MG-RAY]

i... MG-RAY je na tom takmicenju puk'o ko zvecka

[Toce]

Ili da se resenje stavi u spoiler tag!

[MG-RAY]

3. Saksije.

Bastovan Toma je resio da ulepsa svoje prostrano dvoriste tako sto ce ga ukrasiti cvecem. On naime zeli da najpre postavi n saksija u red (1 <= n <= 100000) i da u svakoj od ovh n saksija bude k kilograma zemlje (0 <= k <= 1000), a da potom u njima sadi razno cvece. On je zato od firme koja se bavi prodajom saksija narucio n saksija takvih da se u svakoj od tih n saksija nalazi k kilograma zemlje. Ta firma je bila toliko ljubazna da ne samo donese te saksije vec da ih i postavi u red. Medjutim, sutradan je Toma doziveo veliki shok. Neke saksije imaju vise, a neke manje od k kilograma zemlje. Toma se ipak smirio kada je primetio da je ukupna tezina zemlje u svim saksijama k*n kg. - pa se ova greska da ispraviti. Toma zeli da prebacivanjem zemlje iz jedne saksije u drugu ucini da u svakoj saksiji bude k kilograma zemlje, a da se pri tom najmanje umori. Toma zna da je za prebacivanje x kg. zemlje iz saksije koja je i-ta po redu u saksiju koje je j-ta po redu potrebno da utrosi x * |i - j| dzula energije. Odrediti koliko je minimalno energije koju Toma mora da potrosi da bi ispravio gresku firme koja mu je poslala saksije.

Ulaz: (Ulazni podaci se nalaze u datoteci saksije.in) U prvom redu tekstualne datoteke nalaze se redom celi brojevi n i k. U 2. redu ove datoteke nalazi se n celih brojeva koji su >= 0. Naime i-ti broj (1 <= i <= n) u drugom redu oznacava koliko se kg. zemlje nalazi u i-toj saksiji kada se gleda sa prozora Tomine spavace sobe sa leva na desno.

Izlaz. (Izlazne podatke upisati u datoteku saksije.out) U Izlaznu datoteku treba upisati jedan broj koje je jednak W mod 1000000000, gde je W jednak minimalnom broju dzula koje Toma mora da potrosi da bi ispravio gresku firme od koje je kupio saksije.

Primer 1.
saksije.in
6 4
5 6 2 1 7 3

saksije.out
8

Izvrsavanje programa ne sme da bude duze od 1s. Vazi sa sva 3 zad.

[EclipsE]

MG-RAY kaže:

Izvrsavanje programa ne sme da bude duze od 1s. Vazi sa sva 3 zad.

znachi tu da vas vidim... nema shanse! daju neke test primere od 1000000 (milion) brojeva, ono nije normalno, test fajl 4 MB!

[Marko_L]

Ako je zaista tako, onda je to još jedan dokaz koliko je naše školstvo zapravo loše. Šta znači da radi ispod jedne sekunde ? Na šta se odnosi ? Ako se odnosi na sam algoritam sa limitiranim vrednostima onda ok. Ako se radi o kompletnom procesu, onda to zavisi od veličine ulaznog i izlaznog fajla, kao i od brzine samog računara. Ako je veliki fajl, ponekad samo otvaranje i parsiranje istog može trajati nekoliko sekundi. Uzgred, o kom programskom jeziku se radi ? Mislim, nije da pravi neku bitnu razliku, ali čisto informativno me interesuje.

[sasha vukelic]

prvi je lagan, vjerujem da niste imali problema sa tim, pa idemo dalje

drugi program je, bez uvrede, jos gluplji:

Spoiler za rjesenje:

jedino trebate skontati sta je pobjednicka taktika:

ako navedeni broj nema djelioca (osim 1 i samog sebe, koje na dalje ne racunamo) ocigledno pobjedjuje igrac 1
ako broj ima 1 djelioc opet ocigledno pobjedjuje igrac 2
ako broj ima 2 ili vise djelioca, pobjedjuje igrac 1, sa sljedecom taktikom:

broj (npr 60) se rastavlja na proste faktore (u primjeru: 60=2*2*3*5). neka je N broj faktora (u primjeru N=4). igrac 1 pobjedjuje dijeleci sa proizvodom bilo koja N-2 faktora (u primjeru: igrac 1 pobjedjuje dijeleci sa 2*2, 2*3, 3*5,...)

treci program isto nije narocito tezak (prvobitno sam pomislio da je quicksort, ali je puno lakse):

Spoiler za rjesenje:

punjenje se vrsi redom:

dolazite do prve saksije i ako ona ima vise od K kilograma, punite sljedecu saksiju dok ne dovedete prvu do K kila. ako prva ima manje od K, dovlacite u nju zemlju (iz najblize saksije koja ima zemlje u sebi) dok se ne napuni do K kila. postupak ponavljate za drugu, trecu i sve do predzadnje saksije, uz napomenu da kada "obradite" jednu saksiju, vise je ne dirate!

brzina, naravno, zavisi od racunara, ali i za milion cifara (skupa sa ucitavanjem i pisanjem fajla) bi trebalo biti ispod 10 stotinki...

[MG-RAY]

Marko_L kaže:

Ako je zaista tako, onda je to još jedan dokaz koliko je naše školstvo zapravo loše. Šta znači da radi ispod jedne sekunde ? Na šta se odnosi ? Ako se odnosi na sam algoritam sa limitiranim vrednostima onda ok. Ako se radi o kompletnom procesu, onda to zavisi od veličine ulaznog i izlaznog fajla, kao i od brzine samog računara. Ako je veliki fajl, ponekad samo otvaranje i parsiranje istog može trajati nekoliko sekundi. Uzgred, o kom programskom jeziku se radi ? Mislim, nije da pravi neku bitnu razliku, ali čisto informativno me interesuje.

Misli se na kompletan proces.
C++ (DevC++ IDE)

[Stevvan]

Evo resenje za prvi i drugi,za treci me mrzi da mislim, sad cu da vidim sta je Sasha napisao:

Spoiler za Resenje1:

int main()
{
    char *game = "XOOBOOOOOOOOOOOBOOOOOXOOB";
    unsigned long long int i = 0;
    unsigned long long int suma = 0;
    unsigned long long int trenutna_suma = 0;
    unsigned long long int s = 1;
    int povezani = 0;
    while((game[i] == 'O') || (game[i] == 'B') || (game[i] == 'X'))
    {

        if (game[i] == 'O')
        {
            trenutna_suma+=s;
            s*=2;
            povezani++;
        }
        if (povezani == 15)
        {
            suma=1000000000;
            break;
        }
        else
        {
            if (game[i] == 'B')
            {
                povezani = 0;
                suma+=trenutna_suma;
                s = 1;
                trenutna_suma = 0;
            }
            else if (game[i] == 'X')
            {
                povezani = 0;
                s = 1;
                trenutna_suma = 0;
            }
        }
            i++;
    }

    printf("\n%llu\n",suma);
    return 0;
}

Spoiler za Resenje2:

bool prost(unsigned long int num)
{
    if (num == 1)
        return true;
    for (unsigned long int i = 2; i<= (unsigned long int)sqrt(num);i++)
    {
        if (num%i == 0)
            return false;
    }
    return true;
}


bool ima_koren(unsigned long int n)
{
    double sq = sqrt(n);
    if ((unsigned long int)sq < sq)
        return false;
    return true;
}

unsigned long int delioc(unsigned long int n)
{
    unsigned long int *array;
    array = NULL;
    array = new unsigned long int[1000000];
    unsigned long int count = 0;
    unsigned long int i = n;
    while(!prost(i))
    {
        for (unsigned long int del = 2; del <= sqrt(i);del++)
        {
            if (i%del == 0)
            {
                i/=del;
                array[count] = del;
                break;
            }
        }
        count++;
    }
    array[count] = i;
    unsigned long int p[2] = {0,0};
    count = 0;
    for (unsigned long int g =0; g <=count;g++)
    {
        if (prost(array[g]))
        {
            p[count] = array[g];
            count++;
        }
        if (count == 2)
            break;
    }
    if ((p[0]*p[1] != 0) && (p[0]*p[1] != n))
    {
        return (n/(p[0]*p[1]));
    }
    return p[0];
    delete [] array;
}

int main()
{

    FILE *f;
    f = fopen("igra.in","r");
    int len;
    char line[25];
    fgets(line, 25, f);
    sscanf(line,"%d\n", &len);
    unsigned long int numbers[len];
    for (int i = 0; i < len; i++)
    {
        fgets(line,25,f);
        sscanf(line,"%lu\n",&numbers[i]);
    }
    fclose(f);
    f = fopen("igra.out","w");

    for (int i = 0; i < len; i++)
    {
        int player = 1;
        unsigned long int num = numbers[i];
        while (!prost(num))
        {
            unsigned long int d = delioc(num);
            if (d != 0);
                num/=d;

            player = 3-player;
        }
        char p[20];
        sprintf(p, "%d\n",player);
        fputs(p, f);
    }
    fclose(f);
    return 0;

}

Sledeci put da me je neko od vas dvojice obavestio, hocu i ja da se takmicim

EDIT:
@sasha vukelic:
Lako je reci al treba uraditi, normalno je valjda da svima takva logika pada na pamet

[sasha vukelic]

lako je i uraditi bar sto se tice ova tri zadatka...

al, kao sto je jedan moj prof govorio kada mu se nesto nije dalo: to ostavljamo za zadacu

[pyost]

Marko_L kaže:

Ako je zaista tako, onda je to još jedan dokaz koliko je naše školstvo zapravo loše. Šta znači da radi ispod jedne sekunde ? Na šta se odnosi ? Ako se odnosi na sam algoritam sa limitiranim vrednostima onda ok. Ako se radi o kompletnom procesu, onda to zavisi od veličine ulaznog i izlaznog fajla, kao i od brzine samog računara. Ako je veliki fajl, ponekad samo otvaranje i parsiranje istog može trajati nekoliko sekundi. Uzgred, o kom programskom jeziku se radi ? Mislim, nije da pravi neku bitnu razliku, ali čisto informativno me interesuje.

Zato takmicenje i jeste tesko Sâmi zadaci uglavnom i nisu toliko komplikovani, i sa dovoljno ciklusa se mogu bez problema resiti - cilj je napisati sto optimizovaniji algoritam (brzi sortovi, dinamicko programinje i sl.) tako da i za maksimalne moguce vrednosti (date u zadatku) radi dovoljno brzo.

Pre takmicenja se, naravno, napisu odgovarajuci programi koji rade ispod jedne sekunde za sve ulazne podatke na test masini, gde se posle testiraju i resenja svih takmicara. Dakle, moguce je napisati program koji ispunjava sve uslove, i to je ono sto se trazi od takmicara.

Zadaci se rade u Pascalu, C-u i C++u, a okruzenja su uglavnom Free Pascal (negde moze i Delphi, ali treba uzeti u obzir da se pregleda kôd koji se naknadno kompajlira, pa nesto sto radi u Delphiju ne mora da radi pri testiranju) i DevC++.

Ja sam ove godine odabrao da radim u C++u, iako sam ga prvi put "uzeo u ruke" pre nekoliko nedelja - zgodnija mi je sintaksa, a i treba se navici na jezik za sledecu godinu (kada budem 4. razred), posto mi je tada jako vazan uspeh na drzavnom Ove godine nije bilo bas preterano uspesno, 140/300 u A kategoriji (3, 4. i 5. zadatak), ali i vise nego dovoljno za prolaz Sada samo treba posteno izvezbati grafove, dinamicko i sortiranje

Evo ih i svi zadaci sa resenjima na zvanicnom sajtu:
1. Najslabija karika
2. Igra
3. Saksije
4. Kamencici
5. Krtice

[Letman]

genijalci jel ko uradio 3. , 4. ili 5. zadatak

[Stevvan]

jesam i 3 i 4, stim sto mi 4 ne ide ispod 1 sec trenutno pokusavam ovaj 5 jer je zanimljiviji, pa cu videti da 4 optimizujem, ali necu da koristim klasu vektor...

[EclipsE]

Chak ni njima ne ide ispod jedne sekunde! 4 sek za poslednji primer!

[pyost]

Kako to? Ako se lepo odradi, cetvrti zadatak uopste nije preterano zahtevan

[Stevvan]

Fora kod 4-og je da za svako slovo poseno napravis skladiste (u vidu vektora, zbog lakse upotrebe) gde su mase poredjane redom od najmanje do najvece, posle se samo uzima prva masa (koja je u stvari i najlaksa), i to je sve A slova se mogu skladistiti na foru "neko slovo" - 'A' i time se dobija vrednost od 0 do 26, sto se moze koristiti za niz vektora, gde index prestavlja odredjeno slovo, pa posle nije potrebno ni porediti, sve vec se jednostavno izracuna index od slova tako sto se oduzme 'A' Ne znam jeste li svi razumeli, pa cu napisati source, moj problem je bio sto sam od skora poceo da ucim c++ pa nisam znao za klasu vektor niti koje su njene mogucnosti .

EDIT:
Evo kako sam ja uspeo da optimizujem koliko god sam mogao, na mom kompu za zadnji nacin uradi odmah (kamen.09.in), mada mislim da kada ne bih koristio brisanje prvog clana program bi radio jos brze

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{

    FILE *f;
    f = fopen("kamen.in","r");
    int num, word_len;
    fscanf(f, "%d %d\n", &num, &word_len);

    vector <int> all_letters[26];
    for (int i = 0; i < num; i++)
    {
        char c;
        int m;
        fscanf(f, "%c %d\n", &c, &m);
        all_letters[c-'A'].push_back(m);
    }

    for (int i = 0; i < 26; i++)
    {
        sort(all_letters[i].begin(), all_letters[i].end());
    }

    int mass = 0;
    char c;
    int index;
    for (int i = 0; i < word_len; i++)
    {
        fscanf(f, "%c\n", &c);
        index = c-'A';
        if (all_letters[index].size() == 0)
        {
            mass = -1;
            break;
        }
        else
        {
            mass+=all_letters[index][0];
            all_letters[index].erase(all_letters[index].begin());
        }
    }
    printf("%d\n", mass);
    fclose(f);
    return 0;
}

[pyost]

Nisam ni ja znao za vector pa sam improvizovao sa dve matrice - jedna mi je cuvala podatke, a druga pokazivace ka sledecem elementu po velicini

[Stevvan]

Jel mozemo da vidimo source?