PROPOZICIJE STUDENTSKOG INFORMATIČKOG NATJECANJA

sin(2006).open

"Popcorn"

.natjecanje

Studentsko informatičko natjecanje (SIN) programersko je natjecanje putem Interneta u organizaciji Udruge darovitih informatičara Rijeke (DIR). Ove se godine održava po sedmi put.

Nastavak "OPEN" označava mogućnost sudjelovanja SVIH zainteresiranih, uključujući osnovce, srednjoškolce i studente iz čitave Republike Hrvatske, bez obzira na članstvo u Udruzi.

Natjecatelji se nisu dužni prethodno prijaviti. Ne postoji ni kotizacija. Dovoljno je upoznati se sa ovim propozicijama i predati rješenje u roku.

Natjecanje je otvoreno od 27. studenoga do 17. prosinca 2006. godine. U tom periodu moguće je predati rješenja. Rješenja predana nakon isteka navedenog perioda neće se uzimati u obzir.

.zadatak

.problem

Eto, stigao je film "Borat" i u naša kina. Nepregledne kolone ljudi pohrlile su među prvima vidjeti ovo veličanstveno remek djelo. Gomila ljudi pograbila je karte kako je tko stigao i nestrpljivo čekala njegovo prikazivanje. I došao je taj dan, dan velike premijere. Svi su se okupili ispred kina i to već 3 sata prije početka filma, uzvikujući naizmjenično "Borat, Borat!!!" i "Hoćemo kokice, hoćemo kokice!!!".
Rotkvica, koja se uspješno okušala u raznim profesijama, sada je postala lokalni tajkun zapadnog Balkana i otkupila megalomansku kompaniju "Popcorn" koja se bavi prodajom kokica ispred kinodvorana širom Hrvatske i sebe postavila za glavnog prodajnog menadžera. Kako je znala da je kino rasprodano za premijeru filma, odlučila je unovačiti sve svoje snage kako bi što brže vratila uloženi novac.
Rotkvica ima na raspolaganju N štandova (označimo ih brojevima od 1 do N, 2≤N≤1000), na kojima radi isto toliko zaposlenika tvrtke "Popcorn". Štandovi ne rade ravnomjerno brzo, tako da u jednoj minuti štand br. 1 posluži X1 klijenata, štand broj 2 posluži X2 klijenata, ..., štand broj N posluži XN klijenata. Zarada radnika na štandu broj T u jednoj minuti je XT kuna (dakle, po svakom posluženom klijentu jednu kunu). Osim što, zbog različitih tehnologija, štandovi ne rade istom brzinom (tj., ne pripreme jednaki broj kokica u jednoj minuti), taj podatak se još dodatno mijenja kroz vrijeme, tako da na kraju dobijemo tablicu vrijednosti zarada u svakoj minuti (XAB je (cijeli) broj posluženih klijenata (a time i zarada) u A-toj minuti na štandu broj B, 1≤XAB≤1000).

"Željni zarade i upoznavanja ljudi", zaposlili ste se kod Rotkvice u tvrtki i kao novopečenom radniku Rotkvica je dala posebnu mogućnost dodatne zarade. Naime, nakon svake odrađene minute na štandu br. A, možete se zamijeniti sa radnikom na susjednom štandu (dakle, sa radnicima na štandovima broj A-1 i A+1, ako vrijedi 1 ≤ A-1, A+1 ≤ N) i nastaviti iduću minutu prodavati kokice na tom štandu, nakon čega opet možete mijenjati štand.

Međutim, osim tablice broja posluženih klijenata, postoji i druga, tablica pogreške broja posluženih klijenata. Ta tablica ima istu strukturu kao i prva tablica, a podatak YAB u toj tablici je pogreška u procjeni da će se u A-toj minuti na štandu B poslužiti XAB klijenata i izražena je cjelobrojno, 0≤YAB≤10. To zapravo znači da u A-toj minuti na štandu B broj posluženih klijenata je u intervalu [XAB-YAB, XAB+YAB] (uključujući i granice intervala).

Vaš zadatak je odrediti na kojem štandu ćete se nalaziti svake od M minuta, tako da zaradite što više novaca.

Rješenje zadatka zapišite u M redova, u svakom redu po jedan cijeli broj, gdje broj u K-tom retku predstavlja štand na kome ćete se nalaziti u K-toj minuti, poštujući pravila zadatka.
Rješenje problema ne mora biti jedinstveno.

Format ulazne i izlazne datoteke možete pronaći u primjerima.

.napomene

• Ulazni parametri nalaze se u datoteci ULAZ.TXT, a izvršni programi POPCORN.EXE rješenje treba ispisati u IZLAZ.TXT.
• Bilo kakav ispis na zaslon računala će se prilikom testiranja ignorirati.
• Dozvoljeno je korištenje privremenih datoteka prilikom određivanja rješenja zadatka.
• Programski kod rješenja može biti sastavljen od više datoteka, ali izvršna .EXE verzija programa ne smije ovisiti o drugim datotekama (naravno, osim o datoteci ULAZ.TXT).
• Barem 50% test-primjera imat će tablicu pogreške broja posluženih klijenata jednaku nula (tj., svi YAB u toj tablici bit će jednaki 0).

.primjeri

1. primjer

2. primjer

Fomat datoteka ULAZ.TXT i IZLAZ.TXT

.naputak

Zadatak se treba riješiti u jednom od navedenih programskih jezika: BASIC, Pascal, C/C++, Java.

Rješenje je potrebno OBRAZLOŽITI u sklopu dokumentacije. Poželjno je, ali ne i obvezatno, priložiti dijagram toka. Postojanje i cjelovitost dokumentacije uzimat će se u obzir prilikom bodovanja.

Rješenje će se bodovati prema sljedećim kriterijima:

1. točnost rješenja (broj bodova dobivenih testiranjem)
2. brzina izvođenja programa (brže je bolje)
3. dokumentiranost (kako glavnog algoritma, uključno s dijagramom toka, tako i predanog programa u cjelosti)
4. urednost izvornog koda (čitljivost, originalnost...)

Testni primjeri imaju vremenska ograničenja. Ukoliko program ne generira rješenje u predviđenom roku, prekida se njegovo izvršenje. Tipično vremensko ograničenje po svakom testnom primjeru (odnosno, izvršavanju testnog primjera) iznosi 30 sekundi na računalu Athlon64 3000+, sa 512MB RAMa.

.predajaRješenja

Rješenje se predaje POD ŠIFROM (koju je potrebno navesti u subjectu poruke), kao dio komprimirane datoteke "SIN2006.zip" koja mora sadržavati:

1. rješenja u izvršnom (.exe) obliku (za DOS ili Windows platformu), snimljeno pod imenom "popcorn.exe".
2. izvorni kod rješenja (koji mora odgovarati izvršnoj verziji!).
3. dokumentaciju (čitljivu u Internet Exploreru)
4. "README.txt" datoteku koja mora sadržavati:
4.1 ime i prezime natjecatelja
4.2 punu adresu
4.3 godinu rođenja
4.4 telefonski broj

Rješenje se predaju u privitku (attachment) isključivo e-mailom, na adresu sin@dir.hr, uz ograničenje veličine privitka na 10 MB.

Svaki natjecatelj smije poslati maksimalno tri rješenja gornjeg problema i svako rješenje će se bodovati zasebno.

.nagrade

Dodjeljuje se novčana nagrada u netto iznosu od 1.000,00 kn (slovima: tisuću kuna) prema odluci stručne komisije. Nagradu osvaja natjecatelj(i) koji na testiranju sakupi(e) najviše bodova. DIR zadržava pravo obustave dodjele nagrade ukoliko niti jedno od prispjelih rješenja ne zadovolji minimalne selekcijske kriterije.

Stručna komisija pregledat će prispjela rješenja i ocijeniti ih najkasnije do 25. prosinca 2006. godine.

Proglašenje pobjednika obavit će se putem weba i u medijima. Uručenje nagrade obavit će se u dogovoru s pobjednikom(cima).

.dodatneInformacije

Za sve dodatne informacije možete se obratiti na sin@dir.hr. I... sretno!

U Rijeci, 25. studenog 2006. godine