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

Kolesarji

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 22. marca 2019 (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

Dani so izidi več kolesarskih dirk. Na vsaki od njih je nastopilo istih n kolesarjev in znano je, v kakšnem vrstnem redu so prišli na cilj. Kolesarji dobijo na vsaki tekmi točke glede na mesto, na katero so se uvrstili. Tvoja naloga je sestaviti navidezno kolesarsko ekipo, ki jo sestavlja k kolesarjev. Pred prvo dirko si lahko izbereš poljubnih k kolesarjev, pred vsako naslednjo dirko pa lahko največ m kolesarjev svoje navidezne ekipe zamenjaš z drugimi. Cilj je maksimizirati skupno število točk, ki jih dosežejo kolesarji v tvoji navidezni ekipi. (Pri vsakem kolesarju štejejo njegove točke na vseh tistih dirkah, pri katerih je bil v tvoji navidezni ekipi.)

Primer: recimo, da imamo pet kolesarjev (označeni so s številkami od 1 do 5), tri dirke in da na posamezni dirki kolesar dobi 100 točk za prvo mesto, 80 za drugo, 60 za tretje, 40 za četrto in 30 za peto. Recimo, da so bili izidi posameznih dirk takšni, kot jih kaže spodnja tabela:

Mesto		1.	2.	3.	4.	5.
Točke		100	80	60	40	30
Izidi posameznih dirk	Prva	5	3	2	4	1
	Druga	3	4	5	1	2
	Tretja	1	2	5	3	4

Recimo, da bi radi sestavili navidezno ekipo treh kolesarjev, pri čemer smemo po vsaki dirki največ enega zamenjati. Nekaj možnih scenarijev:

• Pred prvo dirko izberemo kolesarje 1, 2, 3 in nikoli nobenega ne zamenjamo. Tako dobimo (30 + 60 + 80) + (40 + 30 + 100) + (100 + 80 + 40) = 560 točk.
• Pred prvo dirko izberemo kolesarje 1, 2, 4; pred drugo dirko ne zamenjamo nobenega, pred tretjo pa zamenjamo kolesarja 1 s kolesarjem 3. Tako dobimo (30 + 60 + 40) + (40 + 30 + 80) + (80 + 40 + 30) = 430 točk.
• Pred prvo dirko izberemo kolesarje 2, 3, 5; pred drugo dirko zamenjamo kolesarja 2 s kolesarjem 1; pred tretjo dirko zamenjamo kolesarja 3 s kolesarjem 2. Tako dobimo (60 + 80 + 100) + (40 + 100 + 60) + (100 + 80 + 60) = 680 točk.

Možnih je seveda še veliko drugih scenarijev. Izkaže se, da je tisti s 680 točkami najboljši možni, tisti s 430 točkami pa najslabši možni pri teh vhodnih podatkih.

• 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 22. marca 2019.)

Datoteka s tvojo rešitvijo:

Najboljše doslej oddane rešitve

Skupni seštevek

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

Ime in priimek	Rezultat
Gregor Kikelj	270
Tim Poštuvan	210
Matija Bolko	192
Miha Zupan	183
Samo Kralj	166
Jakob Drusany	131
Franci Obid	89
Bartolomej Kozorog	85
Vid Urh	85
Andrej Golčer	55
Uroš Koritnik	54
Matija Kocbek	36

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