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

Barvanje mreže

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 27. marca 2026 (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 n × n polj. Posamezno polje je lahko belo, črno ali rdeče. Rekli bomo, da sta si polji (x₁, y₁) in (x₂, y₂) bližnji, če velja |x₁ − x₂| ≤ d in |y₁ − y₂| ≤ d. Polja ne štejemo za bližnje samemu sebi.

Mreža je veljavna, če ima vsako črno polje vsaj b bližnjih belih polj in kvečjemu c bližnjih črnih polj. Zagotovljeno je, da je mreža v začetnem stanju, kot ga dobimo v vhodnih podatkih, veljavna. Naša naloga je spremeniti nekaj belih polj v črna tako, da mreža ostane veljavna in da bo v mreži čim več parov bližnjih črnih polj.

Primer: recimo, da imamo n = 6, d = 1, b = 1 in c = 5. Naslednja slika kaže nekaj primerov mrež. Prva je vhodna mreža, ostale lahko dobimo iz nje tako, da nekaj belih polj pobarvamo črno.

vhodna mreža (veljavna);
neveljavna mreža: neko črno polje (označeno s križcem) ima preveč bližnjih črnih polj;
neveljavna mreža: neko črno polje (označeno s križcem) ima premalo bližnjih belih polj;
veljavna mreža, na njej je 6 parov bližnjih črnih polj;
veljavna mreža, na njej je 49 parov bližnjih črnih polj.

Mreži (4) in (5) sta torej obe veljavni rešitvi za vhodno mrežo (1), vendar je (5) veliko boljša rešitev kot (4).

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 27. marca 2026.)

Najboljše doslej oddane rešitve

Prikaži podrobno tabelo rezultatov po posameznih testnih primerih.

Testni primer	n	d	b	c	Ime	Ocena oddaje	Točke oddaje
1	30	1	1	7	(še ni rešitev)
2	30	4	9	69	(še ni rešitev)
3	30	7	25	180	(še ni rešitev)
4	100	1	1	7	(še ni rešitev)
5	100	4	9	70	(še ni rešitev)
6	100	13	81	500	(še ni rešitev)
7	300	1	1	8	(še ni rešitev)
8	300	4	9	70	(še ni rešitev)
9	300	13	81	650	(še ni rešitev)
10	1000	1	1	7	(še ni rešitev)
11	1000	13	81	600	(še ni rešitev)
12	1000	40	729	5000	(še ni rešitev)

Skupni seštevek

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

Ime in priimek	Rezultat
(še nihče ni poslal nobene rešitve)

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