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

Pokrajina iz kock

Podroben opis naloge

Iz kock, podobnih lego kockam, bi radi sestavili trodimenzionalni model pokrajine. Pokrajina je opisana z višinskim zemljevidom oz. tlorisom; območje, ki nas zanima, ima v tlorisu obliko pravokotnika, ki ga v mislih razdelimo na karirasto mrežo enotskih kvadratov. Ta mreža ima w stolpcev in h vrstic. Za vsako celico mreže je podana višina pokrajine v tej celici, recimo v[x, y] za celico na preseku stolpca x in vrstice y. Vse te višine so cela števila, večja ali enaka 0.

Primer višinskega zemljevida (w = 4, h = 3) in pripadajoče pokrajine:

0	1	2	0
0	1	3	0
1	0	2	1

„Kocke“, iz katerih sestavljamo naš model pokrajine, so v resnici kvadri različnih velikosti. Možne velikosti kvadrov so podane, za vsako velikost pa imamo na voljo neomejeno število kvadrov tiste velikosti. Kvadre moramo zlagati tako, da se med seboj ne prekrivajo, da ne štrlijo ven iz pokrajine in da pokrijejo celotno pokrajino. Kvadre smemo vrteti v korakih po 90° okrog navpične osi (torej osi z), tako da lahko na primer kvader velikosti a_x × a_y × a_z uporabimo tudi kot kvader velikosti a_y × a_x × a_z. V tvojem modelu pokrajine ne sme biti nobenih votlih delov oz. praznih prostorov pod površjem (četudi bi se dalo s tem morda zmanjšati število potrebnih kvadrov).

Tvoja naloga je sestaviti tak model pokrajine, ki ustreza tem omejitvam in pri tem porabi čim manj kvadrov.

Primer: recimo, da imamo višinski zemljevid z zgornje slike in da so na voljo kvadri naslednjih velikosti: 1 × 1 × 1, 2 × 1 × 1, 3 × 1 × 1, 1 × 1 × 2.

Naslednji dve sliki kažeta dva izmed možnih načinov, kako lahko iz kvadrov takih velikosti sestavimo pokrajino s tega višinskega zemljevida (kvadre na slikah smo pobarvali z različnimi barvami, vendar le zato, da se jih lažje razloči, drugače pa barve ne pomenijo ničesar posebnega):

Rešitev na levi sliki sestavlja 6 kvadrov, rešitev na desni sliki pa 7 kvadrov, zato je leva rešitev boljša od desne.

Naslednja slika pa kaže primer neveljavne rešitve (iz 6 kvadrov):

Ta rešitev je neveljavna zato, ker je na njej kvader nedovoljene velikosti 1 × 1 × 3 (v barvi sivke ). Rekli smo sicer, da so dovoljeni kvadri 3 × 1 × 1 in iz takega kvadra smemo z vrtenjem okrog osi z narediti tudi kvader 1 × 3 × 1 (takega smo dvakrat uporabili na levi rešitvi na prejšnji sliki), ne moremo pa iz njega narediti kvadra 1 × 1 × 3 (saj bi to zahtevalo vrtenje okrog osi y).

Ocenjevalni program

Lahko si preneseš izvorno kodo programa, s katerim bomo ocenjevali prejete rešitve: Rtk21Pokrajina.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 (Pokrajina), 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 z dvema številoma w in h, ki povesta velikost višinskega zemljevida. Sledi h vrstic, ki podajajo vsebino višinskega zemljevida; v vsaki od njih je w števil, ločenih s presledki. Sledi vrstica s številom n, ki pove, koliko različnih velikosti kvadrov je na voljo pri tem testnem primeru. Sledi še n vrstic, ki podajajo te velikosti kvadrov; vsaka od teh vrstic vsebuje tri števila a_x, a_y in a_z, ki pomenijo velikost kvadra vzdolž vseh treh koordinatnih osi.

Primer: če bi imeli en sam testni primer, in sicer tistega iz opisa naloge zgoraj, bi bila vhodna datoteka takšna:

V resnici bo pri tej nalogi 26 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 (Pokrajina). 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. Recimo, da je imel pri tistem testnem primeru višinski zemljevid w stolpcev in h vrstic in da je bila najvišja višina v njem enaka d. Potem mora tvoja rešitev v nadaljevanju vsebovati d · h vrstic, vsaka od teh vrstic pa mora vsebovati po w celih števil, ločenih s po enim presledkom. Pri tem x-to število v (y + (z − 1) · d)-ti od teh vrstic pove številko kvadra, ki mu v tvoji rešitvi pripada enotska kockica s koordinatami (x, y, z). Če ne pripada nobenemu, izpiši tam število 0, sicer pa vsakemu kvadru pripiši neko pozitivno celo število, tako da se bo dalo kvadre ločiti med seboj. Isto število smeš uporabiti pri več različnih kvadrih, če se ne dotikajo skupaj s ploskvijo (smejo pa se dotikati s kakšno stranico ali ogliščem).

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.

To je veljavna rešitev s šestimi kvadri, ki smo jo videli že na eni od zgornjih slik.

Vhodni podatki

pokrajine.in — datoteka z vsemi vhodnimi podatki za to nalogo.
pokrajina-unix.in — ista datoteka, vendar z unixaškimi konci vrstic (LF namesto CRLF).
Če komu pride prav, sta Gregor Kikelj in Domen Hočevar prispevala kodo za branje vhodnih podatkov in izpis rezultatov v pythonu, C++ in javi: na Githubu.

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.