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

Pokrajina iz kock

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 26. marca 2021 (dan pred tekmovanjem).

Kratek opis naloge na tej strani.
Podroben opis naloge in oblike vhodnih ter izhodnih datotek.
Vhodne datoteke.
Registracija (preden lahko oddajaš svoje rešitve).
Obrazec za oddajo tvojih rešitev.
Najboljši doslej oddani rezultati za posamezni testni primer.
Razvrstitev tekmovalcev v skupnem seštevku.

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.

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.

Podrobnejši opis naloge ter vhodnih in izhodnih datotek.
Vhodne datoteke.
Registracija.

Obrazec za oddajo rešitev

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

Najboljše doslej oddane rešitve

Prikaži podrobno tabelo rezultatov po posameznih testnih primerih.

Skrij tabelo rezultatov po posameznih testnih primerih.

Prikazana je najboljša rešitev vsakega uporabnika. Če ima več uporabnikov enako dobre rešitve, so urejeni po času oddaje.

Pri vsakem testnem primeru lahko tekmovalec dobi od 1 do 10 točk, odvisno od svoje uvrstitve (10 za prvo mesto, 8 za drugo, 7 za tretje, . . . , 2 za osmo, 1 za vsa nadaljnja mesta). Kdor za nek testni primer ni oddal nobene veljavne rešitve, dobi pri njem 0 točk.

Testni primer	w	h	d	n	Ime	Ocena oddaje	Točke oddaje
1	1	1	999327	11	Samo Kralj	Ocena oddaje	93	10
					Domen	93	10
					Gregor Kikelj	93	10
					Jošt Smrtnik	93	10
2	995671	1	1	13	Samo Kralj	84	10
					Domen	84	10
					Gregor Kikelj	84	10
					Jošt Smrtnik	85	6
3	100000	1	3	10	Samo Kralj	51320	10
					Domen	53202	8
					Jošt Smrtnik	54840	7
					Gregor Kikelj	56457	6
4	100000	4	1	7	Samo Kralj	45076	10
					Domen	47371	8
					Jošt Smrtnik	48646	7
					Gregor Kikelj	52247	6
5	100000	1	5	7	Samo Kralj	78327	10
					Domen	82907	8
					Jošt Smrtnik	83069	7
					Gregor Kikelj	90673	6
6	100000	6	1	5	Samo Kralj	76826	10
					Domen	81329	8
					Jošt Smrtnik	89242	7
					Gregor Kikelj	94485	6
7	100000	1	9	4	Samo Kralj	154763	10
					Jošt Smrtnik	160392	8
					Domen	164808	7
					Gregor Kikelj	182447	6
8	100000	10	1	3	Samo Kralj	170483	10
					Domen	175210	8
					Jošt Smrtnik	197235	7
					Gregor Kikelj	202176	6
9	20	20	1	3	Samo Kralj	66	10
					Domen	66	10
					Jošt Smrtnik	67	7
					Gregor Kikelj	68	6
10	30	30	1	5	Samo Kralj	108	10
					Domen	115	8
					Jošt Smrtnik	121	7
					Gregor Kikelj	131	6
11	50	50	1	9	Samo Kralj	261	10
					Jošt Smrtnik	283	8
					Gregor Kikelj	286	7
					Domen	287	6
12	20	1	20	4	Samo Kralj	42	10
					Domen	43	8
					Gregor Kikelj	44	7
					Jošt Smrtnik	44	7
13	30	1	30	7	Domen	107	10
					Samo Kralj	108	8
					Gregor Kikelj	109	7
					Jošt Smrtnik	110	6
14	50	1	50	13	Samo Kralj	173	10
					Domen	177	8
					Gregor Kikelj	179	7
					Jošt Smrtnik	181	6
15	10	10	10	6	Samo Kralj	107	10
					Domen	110	8
					Jošt Smrtnik	116	7
					Gregor Kikelj	122	6
16	15	15	15	5	Samo Kralj	467	10
					Domen	480	8
					Jošt Smrtnik	501	7
					Gregor Kikelj	591	6
17	20	20	20	12	Samo Kralj	553	10
					Domen	606	8
					Jošt Smrtnik	640	7
					Gregor Kikelj	675	6
18	40	40	40	23	Samo Kralj	2893	10
					Domen	3075	8
					Jošt Smrtnik	3285	7
					Gregor Kikelj	3483	6
19	50	50	50	23	Samo Kralj	5603	10
					Domen	6000	8
					Jošt Smrtnik	6612	7
					Gregor Kikelj	6726	6
20	100	100	20	27	Samo Kralj	9614	10
					Domen	9829	8
					Jošt Smrtnik	11904	7
					Gregor Kikelj	12576	6
21	100	100	30	27	Samo Kralj	12503	10
					Domen	12875	8
					Jošt Smrtnik	15948	7
					Gregor Kikelj	16809	6
22	100	100	50	27	Samo Kralj	16956	10
					Domen	17871	8
					Jošt Smrtnik	21406	7
					Gregor Kikelj	22938	6
23	100	10	100	12	Samo Kralj	5654	10
					Domen	5852	8
					Gregor Kikelj	6641	7
					Jošt Smrtnik	6788	6
24	20	100	200	12	Samo Kralj	22515	10
					Domen	23194	8
					Gregor Kikelj	24874	7
					Jošt Smrtnik	27705	6
25	100	100	100	27	Samo Kralj	23729	10
					Domen	24031	8
					Jošt Smrtnik	27557	7
					Gregor Kikelj	28360	6
26	300	300	10	12	Samo Kralj	80422	10
					Domen	83634	8
					Jošt Smrtnik	84357	7
					Gregor Kikelj	90030	6

Skupni seštevek

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

Ime in priimek	Rezultat
Samo Kralj	258
Domen	213
Jošt Smrtnik	182
Gregor Kikelj	170

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