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

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

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.

→

→

→

→

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 23. marca 2018.)

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	Opis				Ime	Število pravokotnikov	Točke
Testni primer	w	h	a	b	Ime	Število pravokotnikov	Točke
1	10	10	5	5	Dean Cerin	21	10
					Franci Obid	21	10
					Gregor Kikelj	21	10
					Uroš Koritnik	21	10
					Aleksej Jurca	21	10
					Loris Grmek	22	4
2	10	10	5	5	Gregor Kikelj	14	10
					Dean Cerin	14	10
					Franci Obid	14	10
					Uroš Koritnik	14	10
					Aleksej Jurca	14	10
					Loris Grmek	17	4
3	10	10	4	4	Franci Obid	17	10
					Gregor Kikelj	17	10
					Uroš Koritnik	17	10
					Aleksej Jurca	17	10
					Dean Cerin	18	5
					Loris Grmek	21	4
4	10	10	3	3	Dean Cerin	24	10
					Franci Obid	24	10
					Gregor Kikelj	24	10
					Uroš Koritnik	24	10
					Aleksej Jurca	24	10
					Loris Grmek	30	4
5	30	30	5	5	Franci Obid	127	10
					Gregor Kikelj	127	10
					Aleksej Jurca	127	10
					Dean Cerin	130	6
					Uroš Koritnik	130	6
					Loris Grmek	138	4
6	40	40	5	5	Franci Obid	197	10
					Aleksej Jurca	197	10
					Gregor Kikelj	201	7
					Dean Cerin	203	6
					Uroš Koritnik	208	5
					Loris Grmek	224	4
7	50	50	5	5	Franci Obid	450	10
					Aleksej Jurca	450	10
					Uroš Koritnik	475	7
					Gregor Kikelj	482	6
					Dean Cerin	482	6
					Loris Grmek	561	4
8	60	60	6	6	Aleksej Jurca	643	10
					Franci Obid	643	10
					Uroš Koritnik	683	7
					Gregor Kikelj	695	6
					Loris Grmek	797	5
9	80	80	7	7	Franci Obid	1015	10
					Aleksej Jurca	1015	10
					Uroš Koritnik	1074	7
					Gregor Kikelj	1079	6
					Loris Grmek	1215	5
10	90	90	8	8	Franci Obid	1407	10
					Aleksej Jurca	1407	10
					Uroš Koritnik	1486	7
					Gregor Kikelj	1500	6
					Loris Grmek	1705	5
11	300	299	2	1	Aleksej Jurca	24947	10
					Franci Obid	24958	8
					Uroš Koritnik	25289	7
					Gregor Kikelj	25706	6
					Loris Grmek	30664	5
12	250	273	2	1	Aleksej Jurca	25165	10
					Franci Obid	25200	8
					Uroš Koritnik	25591	7
					Gregor Kikelj	26136	6
					Loris Grmek	31938	5
13	289	296	2	1	Aleksej Jurca	24960	10
					Franci Obid	24961	8
					Uroš Koritnik	25273	7
					Dean Cerin	25301	6
					Gregor Kikelj	25786	5
					Loris Grmek	32912	4
14	276	223	2	1	Dean Cerin	12424	10
					Franci Obid	12424	10
					Aleksej Jurca	12424	10
					Uroš Koritnik	12499	6
					Gregor Kikelj	12503	5
					Loris Grmek	15497	4
15	300	300	3	1	Aleksej Jurca	19806	10
					Franci Obid	19820	8
					Uroš Koritnik	20422	7
					Gregor Kikelj	20486	6
					Loris Grmek	26688	5
16	255	275	3	1	Aleksej Jurca	17011	10
					Franci Obid	17015	8
					Dean Cerin	17138	7
					Uroš Koritnik	17770	6
					Gregor Kikelj	17827	5
					Loris Grmek	24929	4
17	198	293	2	2	Aleksej Jurca	12379	10
					Franci Obid	12394	8
					Gregor Kikelj	12851	7
					Uroš Koritnik	12870	6
					Loris Grmek	14096	5
18	282	235	2	2	Franci Obid	18363	10
					Aleksej Jurca	18363	10
					Uroš Koritnik	18779	7
					Gregor Kikelj	18807	6
					Loris Grmek	21928	5
19	300	10	4	4	Franci Obid	534	10
					Aleksej Jurca	534	10
					Dean Cerin	538	7
					Gregor Kikelj	547	6
					Uroš Koritnik	552	5
					Loris Grmek	587	4
20	9	298	4	4	Franci Obid	470	10
					Aleksej Jurca	470	10
					Dean Cerin	473	7
					Gregor Kikelj	486	6
					Uroš Koritnik	486	6
					Loris Grmek	520	4
21	295	9	3	3	Franci Obid	497	10
					Aleksej Jurca	497	10
					Dean Cerin	501	7
					Uroš Koritnik	506	6
					Gregor Kikelj	510	5
					Loris Grmek	545	4
22	10	292	3	3	Franci Obid	548	10
					Aleksej Jurca	548	10
					Dean Cerin	554	7
					Gregor Kikelj	559	6
					Uroš Koritnik	564	5
					Loris Grmek	612	4
23	300	10	4	4	Franci Obid	607	10
					Aleksej Jurca	607	10
					Dean Cerin	621	7
					Uroš Koritnik	628	6
					Gregor Kikelj	632	5
					Loris Grmek	704	4
24	9	299	4	4	Franci Obid	554	10
					Aleksej Jurca	554	10
					Dean Cerin	579	7
					Uroš Koritnik	582	6
					Gregor Kikelj	583	5
					Loris Grmek	644	4
25	285	10	3	3	Franci Obid	655	10
					Aleksej Jurca	655	10
					Dean Cerin	679	7
					Gregor Kikelj	680	6
					Uroš Koritnik	686	5
					Loris Grmek	764	4
26	9	291	3	3	Franci Obid	590	10
					Aleksej Jurca	590	10
					Uroš Koritnik	604	7
					Dean Cerin	605	6
					Gregor Kikelj	611	5
					Loris Grmek	687	4
27	300	295	8	3	Aleksej Jurca	12649	10
					Franci Obid	12680	8
					Uroš Koritnik	13311	7
					Gregor Kikelj	13334	6
					Loris Grmek	15723	5
28	273	283	8	3	Aleksej Jurca	11945	10
					Franci Obid	11957	8
					Uroš Koritnik	12742	7
					Gregor Kikelj	12743	6
					Loris Grmek	16084	5
29	300	300	8	3	Franci Obid	18099	10
					Aleksej Jurca	18099	10
					Uroš Koritnik	18798	7
					Gregor Kikelj	18901	6
					Loris Grmek	22354	5
30	287	265	8	3	Aleksej Jurca	13826	10
					Franci Obid	13827	8
					Uroš Koritnik	14748	7
					Gregor Kikelj	14808	6
					Loris Grmek	18937	5

Skupni seštevek

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

Ime in priimek	Rezultat
Aleksej Jurca	300
Franci Obid	282
Uroš Koritnik	206
Gregor Kikelj	195
Loris Grmek	132
Dean Cerin	131

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