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

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:

Mesto1.2.3.4.5.
Točke10080604030
Izidi
posameznih
dirk
Prva53241
Druga34512
Tretja12534

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

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.

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

Prikaži podrobno tabelo rezultatov po posameznih testnih primerih.

Skupni seštevek

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

Ime in priimekRezultat
Gregor Kikelj270
Tim Poštuvan216
Matija Bolko206
Samo Kralj187
Franci Obid137
Vid Urh133
Miha Zupan132
Uroš Koritnik82
Andrej Golčer57
Matija Kocbek38

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