PROPOZICIJE STUDENTSKOG INFORMATIČKOG NATJECANJA

sin(2003).open

"Jabučnjak"

.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 četvrti put.

Nastavak "Open" označava mogućnost sudjelovanja SVIH zainteresiranih, 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 25. listopada do 25. studenog 2003. godine. U tom periodu moguće je predati rješenja. Rješenja predana nakon isteka navedenog perioda neće se uzimati u obzir.

.tema

Tema natjecanja, u skladu s aktualnim projektima Udruge, posvećena je projektu "Jabučnjak" - Mac portalu hostanom na adresi mac.dir.hr.

.zadatak

.problem

Mali Tomica u slobodno vrijeme rado pomaže susjedima. Njegovi susjedi, svi odreda, imaju voćnjake i uvijek rado zaposle Tomicu da im pobere njihove brižno pažene voćke. Naravno, sve to uz "odgovarajuću" naknadu. Kako Tomica nema baš neograničeno slobodnog vremena, njemu je u cilju to odraditi što brže i sa što manje truda. No, postoji mali problem: susjedi oko svojih prepunih stabala jabuka imaju zasađenu posebnu englesku travicu i postaju jako nervorzni ako se prolazeći kroz njihov voćnjak zgazi i jedna travka previše. Zato Tomica, da ne bi razljutio svoje poslodavce, prvenstveno gleda da zgazi što manje travice, nastojeći što više puta proći putem koji je već pregazio (jer, naravno, nekud mora proći). Kako je Tomici na raspolaganju samo jedna košara (u koju može stati samo unaprijed zadani broj jabuka!), mora se stalno vraćati na ulaz voćnjaka prazniti košaru. Zato, da se Tomica ne bi previše zamarao kojim putem treba ići kada dođe u voćnjak i gdje pokupiti koliko jabuka, zadatak je pao na vas - naravno, uz "odgovarajuću" naknadu!

Voćnjak je predstavljen sa N točaka i ima oblik konveksnog N-terokuta. Prva rubna točka voćnjaka predstavlja ulaz u voćnjak. Unutar voćnjaka nalazi se M stabala, a na svakom stablu raste određeni broj jabuka (Oj).

Vaš zadatak je pronaći put kojim bi Tomica trebao ići kroz voćnjak tako da prvenstveno zgazi što manje travice (tj. da ostavi što više travice netaknuto), te da prevali najmanji mogući put skupljajući jabuke.

.ulazniPodaci

U prvom retku tekstualne datoteke JABUKE.IN nalazi se prirodni broj V - broj voćnjaka koje Tomica mora obrati (V ≤ 10). U narednim retcima opisan je svaki od voćnjaka i to na sljedeći način:

* U narednom retku nalazi se prirodni broj N (broj točaka kojima je jednoznačno određen izgled voćnjaka, N ≤ 100), prirodni broj M (broj stabala jabuka u voćnjaku, M ≤ 100), te prirodni broj O (veličina košare, tj. maksimalni broj jabuka koji stane u košaru, O ≤ 1000).
* U narednih N redaka nalaze se parovi realnih brojeva Xi i Yi (koordinate svake pojedine točke koja predstavlja rub voćnjaka – one tvore konveksni n-terokut), gdje prvi par brojeva predstavlja ulaz u voćnjak.
U sljedećih M redaka nalaze se po tri realna brojeva Xj i Yj (koordinate stabala u voćnjaku), te Oj (broj jabuka na odgovarajućem stablu, Oj ≤ 100).

Svi podaci koji predstavljaju koordinate neke točke biti će u rasponu [-100,100]. Svi podaci unutar jednog retka biti će odvojeni razmakom.

.izlazniPodaci

U tekstualnu datoteku JABUKE.OUT potrebno je ispisati put kojim se Tomica mora kretati, kao i koliko jabuka uzeti sa pojedinog stabla trenutnog voćnjaka tako da se u svakom retku ispiše ili:

1) Dva cijela broja (odvojena jednim razmakom), pri čemu prvi predstavlja redni broj stabla prema kojem se Tomica kreće (redoslijed stabala je određen redoslijedom zapisa u ulaznoj datoteci), a drugi broj predstavlja broj jabuka koje je potrebno ubrati sa navedenog stabla i staviti u košaru.
2) 0 (nula), ako se Tomica kreće prema ulazu u voćnjak (dolaskom na ulaz, prazni se košara).

Rješenja za pojedine voćnjake potrebno je odvojiti jednim praznim retkom.

.napomena

Rješenje ne mora biti jedinstveno!

.primjer

.naputak

Zadatak se mora riješiti u jednom od navedenih programskih jezika: BASIC, Pascal, C.

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. dokumentiranost (kako glavnog algoritma, uključno s dijagramom toka, tako i predanog programa u cjelosti)
3. brzina izvođenja programa (brže je bolje)
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 iznosi 60 sekundi na računalu klase PII 300MHz s barem 500K memorije slobodne za program.

Svi ulazni podaci čitaju se iz tekstualne datoteke ("jabuke.in") koja se nalazi u tekućem direktoriju. Program ne smije čekati na unos sa tipkovnice. Izlazne podatke također je potrebno zapisivati u tekući direktorij (u tekstualnu datoteku "jabuke.out").

.predajaRješenja

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

1. rješenje u izvršnom (.exe) obliku (za DOS, Linux, Windows ili Mac OS X), snimljeno pod imenom "jabuke.exe"
2. rješenje u izvornom kodu (koji mora odgovarati izvršnoj verziji!), snimljeno pod imenom "jabuke.bas", "jabuke.pas" ili "jabuke.c"
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
4.5 oznaku operativnog sustava za koji je predana izvršna verzija programa (DOS/Linux/WIN/MAC)

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

Broj predanih rješenja po pojedinom natjecatelju NIJE ograničen.

.nagrade

Dodjeljuje se SAMO JEDNA novčana nagrada u neto iznosu od 1.000,00 kn (slovima: tisuću kuna) prema odluci stručne komisije. Nagradu osvaja natjecatelj koji na testiranju sakupi 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 ocjeniti ih do 10. prosinca 2003. godine.

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

.dodatneInformacije

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

U Rijeci, 25. listopada 2003. godine