Srednješolsko tekmovanje ACM iz računalništva in informatike

Risanje s pravokotniki

To je „off-line naloga“. Na tej spletni strani je objavljen opis naloge in testni primeri. Svoje rešitve lahko pošlješ prek obrazca na tej strani kadarkoli do vključno 23. marca 2018 (dan pred tekmovanjem).

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. 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.

Obrazec za oddajo rešitev

(Oddaja rešitev je možna do vključno 23. marca 2018.)

Datoteka s tvojo rešitvijo:

Najboljše doslej oddane rešitve

Prikaži podrobno tabelo rezultatov po posameznih testnih primerih.

Skupni seštevek

V skupnem seštevku se za vsakega tekmovalca seštejejo njegove točke z vseh testnih primerov.

Ime in priimekRezultat
Franci Obid300
Gregor Kikelj239
Dean Cerin149

[H kazalu. | Na vrh te strani. | Imate vprašanje ali komentar?]