Srednješolsko tekmovanje ACM iz računalništva in informatike
Poplavljanje
Podroben opis naloge
Dana je karirasta mreža, v kateri je vsaka celica pobarvana z določeno barvo. Barve celic lahko spreminjamo, vendar le na naslednji način: izberemo si neko barvo in začnemo mrežo „poplavljati“ z njo v zgornji levi celici. Nova barva se iz zgornje leve celice razširi tudi na tiste njene sosede, ki so bile prej enake barve kot ona, iz njih pa spet na tiste njihove sosede, ki so bile prej enake barve kot zgornja leva celica, in tako naprej na vse celice, ki so dosegljive na ta način. (Celici veljata za sosednji, če imata skupno eno od stranic.)
Tvoja naloga je s čim manj takšnimi poplavljanji doseči, da bodo vse celice mreže pobarvane z isto barvo (ni važno, katero).
Primer mreže in enega od možnih zaporedij poplavljanj:
- Na spletni strani Simona Tathama se lahko preizkusite v ročnem poplavljanju takšnih mrež.
Ocenjevalni program
Lahko si preneseš izvorno kodo programa, s katerim bomo ocenjevali prejete rešitve: Rtk22Poplavljanje.cpp.
Na voljo je tudi prevedena različica ocenjevalnega programa (za Windows).
Oblika vhodne datoteke
Pri tej nalogi so vsi testni primeri podani v eni vhodni datoteki. V prvi vrstici vhodne datoteke je niz z imenom naloge (Poplavljanje), v drugi pa število testnih primerov (T). Sledijo testni primeri, pred vsakim od njih pa je še ena prazna vrstica.
Vsak testni primer se začne z vrstico, ki vsebuje številko tega testnega primera (od 1 do T). Sledi vrstica s tremi števili: w (širina mreže), h (višina mreže) in b (število barv v začetnem stanju mreže). Sledi h vrstic, ki podajajo začetno stanje mreže; v vsaki od njih je w števil (ločenih s presledki), ki predstavljajo barve celic v tej vrstici mreže. Barve so predstavljene z naravnimi števili od 1 do b.
Primer: če bi imeli en sam testni primer, in sicer tistega iz opisa naloge zgoraj, bi bila vhodna datoteka lahko takšna:
Poplavljanje 1 1 5 4 4 3 2 2 4 4 3 3 2 1 2 1 3 4 2 2 3 2 4 1 3
V resnici bo pri tej nalogi 30 testnih primerov.
Oblika izhodne datoteke
Oddaš lahko poljubno število izhodnih datotek s svojimi rešitvami. Pri tem vsaka izhodna datoteka vsebuje rešitve za enega ali več testnih primerov. Če za isti testni primer oddaš več rešitev, bomo pri ocenjevanju upoštevali najboljšo med njimi.
Oblika posamezne izhodne datoteke je naslednja:
V prvi vrstici naj bo koda, ki si jo dobil(a) ob registraciji in iz katere je razvidno, da si rešitev res poslal(a) ti, ne pa kdo drug. V drugi vrstici naj bo ime naloge (Poplavljanje). Sledijo naj tvoje rešitve za enega ali več testnih primerov.
Vsaka rešitev se začne s prazno vrstico. Sledi naj vrstica, ki vsebuje številko testnega primera (od 1 do T), na katerega se ta rešitev nanaša. V drugi vrstici naj bo število poplavljanj, ki tvorijo tvojo rešitev. V tretji vrstici naj bo zaporedje števil, ki po vrsti za vsako poplavljanje povedo, katero barvo si uporabil(a) pri njem. To naj bodo naravna števila od 1 do b (pri čemer je b število barv pri tistem testnem primeru, na katerega se ta rešitev nanaša), ločena s po enim presledkom. Poplavljanj sme biti največ w · h, torej toliko, kolikor je celic na mreži pri tem testnem primeru.
Primer: če bi bila naša uporabniška koda enaka 123456 in bi obstajal prvi testni primer, kakršen je prikazan zgoraj, bi lahko oddali spodnjo izhodno datoteko.
123456 Poplavljanje 1 5 2 4 1 3 2
To je veljavna rešitev s petimi poplavljanji, ki smo jo videli že na sliki zgoraj.
Vhodni podatki
- poplavljanje.in — datoteka z vsemi vhodnimi podatki za to nalogo.
- poplavljanje-unix.in — ista datoteka, vendar z unixaškimi konci vrstic (LF namesto CRLF).
- Zgolj informativno so na voljo tudi vizualizacije vseh testnih primerov.
Registracija
Preden lahko oddajaš svoje rešitve, se prijavi prek spodnjega obrazca. Dodelili ti bomo enolično uporabniško kodo, ki jo boš potreboval(a) za pripravo svojih izhodnih datotek.
Opomba: pri tej nalogi lahko sodeluje kdorkoli, ne glede na starost, izobrazbo, itd. Objavili bomo rezultate vseh tekmovalcev, za morebitne praktične nagrade pa pridejo v poštev le srednješolci/ke in študentje/ke.
Obrazec za oddajo rešitev
(Oddaja rešitev je možna do vključno 25. marca 2022.)
[Nazaj na glavno stran. | Na vrh te strani. | Imate vprašanje ali komentar?]