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.

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 neki testni primer ni oddal nobene veljavne rešitve, dobi pri njem 0 točk.

Testni primer	Št. krogov n	Ime	Ocena oddaje	Točke oddaje
1	33	Rok Kralj	0.000000000000	10
		Samo Kralj	0.000000000000	10
		Matej Kralj	0.000000000000	10
		Luka Stražišar	0.000086314470	6
		Timotej Kobe	0.004238803434	5
2	50	Luka Stražišar	0.000000000000	10
		Matej Kralj	0.000000000000	10
		Rok Kralj	0.000000000000	10
		Samo Kralj	0.000000000000	10
		Timotej Kobe	0.000000000000	10
3	80	Rok Kralj	0.002116063021	10
		Samo Kralj	0.002154250401	8
		Matej Kralj	0.002837409401	7
		Luka Stražišar	0.021761871002	6
		Timotej Kobe	0.028586325817	5
4	30	Luka Stražišar	0.000000000000	10
		Matej Kralj	0.000000000000	10
		Rok Kralj	0.000000000000	10
		Samo Kralj	0.000000000000	10
		Timotej Kobe	0.000000000000	10
5	40	Rok Kralj	0.016200670045	10
		Samo Kralj	0.018732705323	8
		Matej Kralj	0.023294998217	7
		Luka Stražišar	0.039640009860	6
		Timotej Kobe	0.047767143054	5
6	211	Luka Stražišar	0.000000000000	10
		Matej Kralj	0.000000000000	10
		Rok Kralj	0.000000000000	10
		Samo Kralj	0.000000000000	10
		Timotej Kobe	0.011640285925	5
7	23	Rok Kralj	0.027757517337	10
		Matej Kralj	0.027757532077	8
		Samo Kralj	0.027757555903	7
		Timotej Kobe	0.033228197402	6
		Luka Stražišar	0.033608849413	5
8	18	Luka Stražišar	0.000000000000	10
		Matej Kralj	0.000000000000	10
		Rok Kralj	0.000000000000	10
		Samo Kralj	0.000000000000	10
		Timotej Kobe	0.001070987806	5
9	28	Luka Stražišar	0.000000000000	10
		Matej Kralj	0.000000000000	10
		Rok Kralj	0.000000000000	10
		Samo Kralj	0.000000000000	10
		Timotej Kobe	0.000174961136	5
10	18	Matej Kralj	1.694316289782	10
		Rok Kralj	1.694316290331	8
		Samo Kralj	1.694316953295	7
		Luka Stražišar	1.728480534178	6
		Timotej Kobe	1.736954903688	5
11	127	Matej Kralj	0.476168323755	10
		Rok Kralj	0.476181824210	8
		Samo Kralj	0.476271976899	7
		Timotej Kobe	0.501264153116	6
		Luka Stražišar	0.524502475716	5
12	99	Rok Kralj	0.988718753263	10
		Matej Kralj	0.988761428960	8
		Samo Kralj	0.988868646752	7
		Timotej Kobe	1.007331229287	6
		Luka Stražišar	1.034098160249	5
13	481	Rok Kralj	1.662390024642	10
		Samo Kralj	1.689799699194	8
		Matej Kralj	1.927128759062	7
		Luka Stražišar	1.944856548097	6
		Timotej Kobe	3.746934581866	5
14	40	Rok Kralj	2.811748934187	10
		Matej Kralj	2.812115113289	8
		Samo Kralj	2.814477954829	7
		Timotej Kobe	2.893574046247	6
		Luka Stražišar	2.918246907740	5
15	89	Rok Kralj	1.483389898549	10
		Samo Kralj	1.484422206714	8
		Timotej Kobe	1.569842291443	7
		Luka Stražišar	1.649050129017	6
		Matej Kralj	1.875724274090	5
16	193	Rok Kralj	3.489657820671	10
		Samo Kralj	3.501146673060	8
		Timotej Kobe	3.599299610073	7
		Matej Kralj	3.886851702215	6
		Luka Stražišar	3.900860787653	5
17	60	Rok Kralj	13.241998522149	10
		Matej Kralj	13.246041890796	8
		Samo Kralj	13.247294730326	7
		Timotej Kobe	13.429629262403	6
		Luka Stražišar	13.542346779072	5
18	234	Rok Kralj	3.643046008476	10
		Samo Kralj	3.660100913507	8
		Matej Kralj	3.895900573341	7
		Luka Stražišar	3.919413859447	6
		Timotej Kobe	4.009967335866	5
19	109	Matej Kralj	0.494516392042	10
		Rok Kralj	0.494737287074	8
		Samo Kralj	0.494741726587	7
		Timotej Kobe	0.524383743559	6
		Luka Stražišar	0.535832220613	5
20	703	Rok Kralj	33.383197341313	10
		Samo Kralj	33.393460451298	8
		Matej Kralj	33.800032777961	7
		Luka Stražišar	35.026366894613	6
		Timotej Kobe	45.353599457454	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
Rok Kralj	194
Matej Kralj	168
Samo Kralj	165
Luka Stražišar	133
Timotej Kobe	120

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