SIN(2004).open

Udruga darovitih informatičara Rijeke
objavljuje

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

Nastavak "OPEN" označava mogućnost sudjelovanja SVIH zainteresiranih, uključujući osnovce i srednjoškolce 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 01. prosinca do 31. prosinca 2004. godine. U tom periodu moguće je predati rješenja. Rješenja predana nakon isteka navedenog perioda neće se uzimati u obzir.

Tema natjecanja, u skladu s aktualnim projektima Udruge, posvećena je projektu "Torpedo" - multimedijalnoj igri koja se prikazuje na lokalnoj televiziji "Kanal Ri".

Naši svevremenski junaci Rotkvica i Mirko opet su s nama. Zaželjeli ste ih se, zar ne? Sigurno se pitate što im sada treba? Ako ne, onda stvarno ne znam zašto ovo uopće čitate! Možda nagrade imaju veze s tim ...

Dakle, da krenemo! Već spomenuti, Rotkvica i Mirko igraju igru potapanje brodova. Za sve one koji ne znaju, za navedenu igru potrebna vam je ploča sa M redaka i N stupaca. Na početku igre određuje se kakvi će se brodovi koristiti u igri (tj. njihovi oblici, veličina i broj), te svaki igrač u najvećoj tajnosti postavlja brodove na ploču. Jedino pravilo prilikom postavljanja brodova je da se brodovi ne smiju preklapati niti dodirivati (čak niti po dijagonali)! Nakon toga svaki igrač naizmjeničko pokušava pogoditi gdje je protivnički igrač postavio brodove „otvarajući“ polja odabirom retka i stupca. Jedini odgovor koji protivnik može dati je:

* "POGODAK" – na odabranom polju nalazi se neki dio broda, ali cijeli brod još nije potopljen;
* "PROMAŠAJ" – na odabranom polju ne nalazi se brod;
* "POTOP" – odabrano polje sadrži brod ili dio broda, te je ovim pogotkom potopljen i cijeli brod.

Pobjednik igre je onaj igrač koji prvi potopi sve protivničke brodove!

Super, ali sigurno se pitate kakve to veze ima s Vama? Vaš zadatak je da na osnovu prethodno objašnjenog načina igranja napravite dva programa BROD i IGRA, gdje prvi program (BROD) na osnovu dobivenih ulaznih podataka slaže brodove na igraču ploču, a drugi program (IGRA) pokušava pogoditi sve brodove složene na takvu ploču (naravno, ne nužno od vašeg programa BROD :)).

U tekstualnoj datoteci BROD.IN nalaze se podaci potrebni za početak igre složeni na sljedeći način:
* u prvom retku datoteke nalaze se dva prirodna broja M i N odvojena jednim razmakom (M,N ≤ 1000) što označava broj redaka i stupaca ploče na kojoj se igraju Rotkvica i Mirko.
* u drugom retku datoteke nalazi se prirodni broj X (X ≤ 100) broj brodova koje treba postaviti na ploču.
* u narednih X redova datoteke nalazi se par prirodnih brojeva A,B (A,B ≤ 1000) gdje je A širina, a B duljina broda (brodove prilikom smještanja možemo rotirati za 90 stupnjeva). Brod uvijek zauzima puni pravokutnik.

* Ulazni podaci će biti takvi tako da će se uvijek moći generirati barem jedan raspored brodova.
* Rješenje nije jedinstveno.

U tekstualnu datoteku BROD.OUT potrebno je ispisati točno jedan način kako se mogu svi brodovi postaviti na igraču ploču. U svakom od M redova izlazne datoteke treba se nalaziti po N znakova, gdje 0 predstavlja mjesto gdje nema broda, a 1 predstavlja mjesto gdje se nalazi brod ili neki njegov dio!

BROD.IN 5 5 2 2 2 1 2	BROD.IN 4 5 3 2 1 3 1 2 2	BROD.IN 9 10 4 5 5 4 4 5 3 4 4
BROD.OUT 00000 00011 00011 00000 00011	BROD.OUT 10011 10011 00000 00111	BROD.OUT 1111101111 1111101111 1111101111 1111101111 1111100000 0000001111 1111101111 1111101111 1111101111

Objašnjenje drugog primjera: Na ploči od 4 redaka i 5 stupaca postavljamo tri broda, prva dva su pravokutnog oblika, a treći kvadratnog veličine stranice 2.

Ulazni podaci za program IGRA sastoje se od prethodno opisane datoteke BROD.IN te od točno jednog parametra uz poziv programa. Svaki poziv automatski uključuje i nekakvu akciju koju treba poduzeti program prilikom njegovog poziva s navedenim parametrom.

Rezultat svakog poziva programa trebaju biti dva broja koja označavaju redom redak i stupac koji igrač "gađa" (ispisuju se na zaslon računala, odvojena jednim razmakom).

Parametar uz poziv programa IGRA	Objašnjenje akcije
START	Navedeni parametar označava da u tom trenutku igrač počinje sa igrom. Kao što je već navedeno, podaci o izgledu igrače ploče nalaze se u datoteci BROD.IN.
POGODAK	Prethodni hitac rezultirao je potapanjem dijela, ali ne i cijelog broda.
PROMASAJ	Prethodni hitac promašio je sve mete na igračoj ploči.
POTOP	Prethodni hitac potopio je cijeli brod (ili njegov posljednji nepotopljeni dio).
KRAJ	Prethodni hitac potopio je i posljednji nepotopljeni brod, te je igra završena.

* prilikom izvršavanja programa smije se koristiti do 1000 pomoćnih datoteka (od IGRA0000.TMP do IGRA9999.TMP), te se zbog neprestanog pozivanja svi međurezultati trebaju upisivati u navedene datoteke koje se neće brisati sve do završetka posljednjeg poziva programa IGRA (sa parametrom KRAJ).
* Cilj igre je pogoditi sve brodove u što manjem broju hitaca.

Podaci u BROD.IN
3 3 2 1 1 1 2	0 0 1 1
Potencijalni raspored brodova koji nije poznat igraču/programu
001 100 100	00 11
Logika igre prilikom izvršavanja (ne označava najbolje moguće rješenje)
IGRA START (izlaz na zaslonu): 1 1 IGRA PROMASAJ (izlaz na zaslonu): 1 2 IGRA PROMASAJ (izlaz na zaslonu): 1 3 IGRA POTOP (izlaz na zaslonu): 2 1 IGRA POGODAK (izlaz na zaslonu): 3 1 IGRA KRAJ	IGRA START (izlaz na zaslonu): 1 1 IGRA PROMASAJ (izlaz na zaslonu): 2 1 IGRA POGODAK (izlaz na zaslonu): 1 2 IGRA PROMASAJ (izlaz na zaslonu): 2 2 IGRA KRAJ

Zadaci se moraju 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.

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 (odnosno, izvršavanju testnog primjera) iznosi 30 sekundi na računalu klase PIV 1.8GHz s barem 32MB heap memorije i 4MB stack memorije slobodne za program.

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

1. rješenja u izvršnom (.exe) obliku (za DOS ili Windows platformu), snimljeno pod imenom "brod.exe" i "igra.exe".
2. izvorne kodove rješenja (koji moraju odgovarati izvršnim verzijama!).
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.

Dodjeljuje se 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 ocijeniti ih do 15. siječnja 2005. godine.

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