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

Zlaganje krogov

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 21. marca 2025 (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.
Rezultati.
Najboljši doslej oddani rezultati za posamezni testni primer.
Razvrstitev tekmovalcev v skupnem seštevku.

Opis naloge

Danih je n krogov s polmeri r₁, r₂, …, r_n. Tvoja naloga je razporediti te kroge po ravnini tako, da bodo njihova središča vsa ležala znotraj enotskega kvadrata (koordinate središč morajo biti torej z intervala [0, 1]), krogi pa se bodo čim manj prekrivali. Natančneje povedano, če za vsak par krogov izračunamo ploščino njunega preseka in te ploščine seštejemo, si želimo, da bi bila ta vsota čim manjša. (To pomeni, da če se na nekem območju prekriva natanko k krogov, se ploščina tega območja šteje kar k · (k − 1)/2-krat.)

Primer: recimo, da moramo razporediti štiri kroge s polmeri 1/10, 1/5, 1/2 in 7/10. Naslednja slika kaže tri primere takšnih razporedov (možnih je seveda še neskončno mnogo drugih razporedov). Črne pike so središča krogov; pobarvana so območja, kjer se krogi prekrivajo (modra = prekrivata se natanko dva kroga; zelena = prekrivajo se natanko trije krogi; rdeča = prekrivajo se vsi štirje krogi); črtkane črte označujejo enotski kvadrat.

Prva od teh rešitev je zelo slaba, saj se krogi močno prekrivajo. Druga je že veliko boljša, tretja pa je optimalna, saj se krogi pri njej sploh ne prekrivajo več. (V splošnem seveda ni nujno, da je dane kroge sploh mogoče razporediti tako, da se ne prekrivajo; za tale konkretni nabor štirih krogov pa je to vendarle mogoče.)

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 21. marca 2025.)

Najboljše doslej oddane rešitve

Prikaži podrobno tabelo rezultatov po posameznih testnih primerih.

Testni primer	Št. krogov n	Ime	Ocena oddaje	Točke oddaje
1	33	Matej Kralj	0.000004	10
Luka Stražišar	0.001406	8
Rok Kralj	0.109353	7
2	50	Luka Stražišar	0.000000	10
Matej Kralj	0.000000	10
3	80	Matej Kralj	0.024091	10
Luka Stražišar	0.032944	8
4	30	Luka Stražišar	0.000000	10
Matej Kralj	0.000000	10
5	40	Matej Kralj	0.044090	10
Luka Stražišar	0.053716	8
6	211	Luka Stražišar	0.000000	10
Matej Kralj	0.000000	10
7	23	Rok Kralj	0.030514	10
Matej Kralj	0.051430	8
Luka Stražišar	0.064402	7
8	18	Luka Stražišar	0.000000	10
Matej Kralj	0.000000	10
9	28	Luka Stražišar	0.000000	10
Matej Kralj	0.000000	10
10	18	Rok Kralj	1.700568	10
Matej Kralj	1.723140	8
Luka Stražišar	1.870438	7

Skupni seštevek

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

Ime in priimek	Rezultat
Matej Kralj	96
Luka Stražišar	88
Rok Kralj	27

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