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

Zlaganje likov

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 20. marca 2015 (dan pred tekmovanjem).

Opis naloge

Dano je veliko število likov iz igre Tetris. Naloga je zložiti like v večji lik s čim manjšim obsegom, pri čemer se liki med seboj ne smejo prekrivati. Pri tem je novi „lik“ lahko tudi sestavljen iz več nepovezanih delov, lahko vsebuje luknje ipd. Obseg je definiran kot skupna dolžina vseh robov, pri katerih liki mejijo na belo podlago naše kariraste mreže (namesto na druge like).

Možne oblike likov so naslednje:

Primer: recimo, da imamo naslednje like:

Teh pet likov lahko zložimo na veliko različnih načinov in dosežemo različno velike obsege. Spodnja slika prikazuje tri izmed njih in pod vsakim še njegov obseg:

Med temi tremi razporedi je torej najboljši tisti v sredini, ki ima obseg samo 20 enot.

Obrazec za oddajo rešitev

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

Datoteka s tvojo rešitvijo:

Najboljši doslej oddani razporedi

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
Tomaž Hočevar2893
Rok Kralj2385
David Fabijan2100
Miloš Ljubotina2056
Rok Lampret1691
Patrik Zajec1368
Dean Cerin536
Tomaž Tomažič329
Tadej Vodopivec56

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