Srednješolsko tekmovanje ACM iz računalništva in informatike
Risanje s pravokotniki
Podroben opis naloge
Dana je karirasta mreža, na kateri so na začetku vse celice bele. Na tej mreži lahko rišemo črne pravokotnike, pri čemer je največja velikost posameznega pravokotnika omejena. Predpisano je končno stanje mreže, ki ga hočemo na ta način doseči (torej nekakšna črno-bela slika, ki jo hočemo narisati). Naloga je poiskati čim manjši nabor pravokotnikov, ki doseže zahtevano končno stanje. Pravokotniki se smejo med seboj tudi prekrivati, ne smejo pa štrleti ven iz mreže. Vrstni red, v katerem pravokotnike rišemo, ni pomemben.
Primer: recimo, da imamo mrežo 3 × 3 celic, v kateri bi radi na koncu dosegli takšno stanje:
Če so največji dovoljeni pravokotniki velikosti 2 × 2, lahko to naredimo že z dvema pravokotnikoma.
|
|
→ |
|
→ |
|
Če so največji dovoljeni pravokotniki velikosti 3 × 1 (ali 1 × 3), potrebujemo vsaj tri pravokotnike.
|
|
→ |
|
→ |
|
→ |
|
Če so največji dovoljeni pravokotniki velikosti 2 × 1 (ali 1 × 2), potrebujemo vsaj štiri pravokotnike.
|
|
→ |
|
→ |
|
→ |
|
→ |
|
Ocenjevalni program
Lahko si preneseš izvorno kodo programa, s katerim bomo ocenjevali prejete rešitve: Rtk18Pravokotniki.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 (Pravokotniki), v drugi pa število testnih primerov (T). Sledijo testni primeri, pred vsakim od njih pa je še ena prazna vrstica.
Posamezni testni primer se začne z vrstico, ki vsebuje pet celih števil, ločenih s po enim presledkom: številka testnega primera (od 1 do T), širina mreže w (od 1 do 1000), višina mreže h (od 1 do 1000), nato pa še dve števili a in b, ki povesta največjo dovoljeno velikost posameznega pravokotnika. Pomen teh dveh števil je naslednji: pri posameznem pravokotniku mora biti bodisi širina kvečjemu a in višina kvečjemu b bodisi mora biti širina kvečjemu b in višina kvečjemu a.
Sledi še h vrstic, v vsaki od njih pa je po w znakov, ki opisujejo želeno ciljno stanje mreže. Pri tem znak . (pika) pomeni celico, ki mora ostati bela, znak # pa pomeni celico, ki jo moramo z vsaj enim od pravokotnikov pobarvati črno.
Primer: če bi imeli en sam testni primer, in sicer tistega z začetka tega opisa, in če bi dovolili pravokotnike velikosti največ 1 × 3 oz. 3 × 1, bi bila vhodna datoteka takšna:
Pravokotniki 1 1 3 3 1 3 ##. ### .##
V resnici bo pri tej nalogi 30 testnih primerov; za ilustracijo je tule prvih nekaj vrstic prave vhodne datoteke:
Pravokotniki 30 1 10 10 5 5 .#.......# ###.#..##.
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 (Pravokotniki). Sledijo naj tvoje rešitve za enega ali več testnih primerov.
Vsaka rešitev se začne s prazno vrstico. V drugi vrstici naj bo številka testnega primera, na katerega se nanaša ta rešitev. Sledi naj vrstica, ki vsebuje število narisanih pravokotnikov (recimo mu n; veljati mora 1 ≤ n ≤ w · h, pri čemer sta w in h dimenziji mreže pri tem testnem primeru). Sledi naj n vrstic, ki opisujejo te pravokotnike. Vsak pravokotnik naj bo opisan s štirimi celimi števili, ločenimi s po enim presledkom: najprej x-koordinata najbolj levega stolpca tega pravokotnika (pri tem x = 0 pomeni najbolj levi stolpec mreže, x = w − 1 pa najbolj desni stolpec mreže), nato y-koordinata najbolj zgornje vrstice tega pravokotnika (pri tem y = 0 pomeni najbolj zgornjo vrstico mreže, y = h − 1 pa najbolj spodnjo vrstico mreže), nato širina tega pravokotnika in nazadnje še višina tega pravokotnika.
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 Pravokotniki 1 4 0 1 3 1 1 0 1 3 0 0 1 1 2 1 1 2
Ta rešitev je veljavna, ni pa najboljša možna, ker uporabi štiri pravokotnike namesto treh.
Vhodni podatki
- pravokotniki.in — datoteka z vsemi vhodnimi podatki za to nalogo.
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 23. marca 2018.)
[Nazaj na glavno stran. | Na vrh te strani. | Imate vprašanje ali komentar?]