Srednješolsko tekmovanje ACM iz računalništva in informatike
Kolesarji
Podroben opis naloge
Dani so izidi d kolesarskih dirk. Na vsaki od njih je nastopilo istih n kolesarjev (ki so označeni s celimi števili od 1 do n) 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, in sicer kolesar na i-tem mestu dobi ti točk. (Nikoli se ne zgodi, da bi si dva ali več kolesarjev delilo isto mesto na isti dirki; lahko pa se zgodi, da kolesarji na različnih mestih dobijo enako število točk, torej da je npr. ti = ti + 1.)
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 n = 5 kolesarjev, d = 3 dirke in da na posamezni dirki kolesar dobi t1 = 100 točk za prvo mesto, t2 = 80 za drugo, t3 = 60 za tretje, t4 = 40 za četrto in t5 = 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 k = 3 kolesarjev, pri čemer smemo po vsaki dirki največ enega zamenjati (m = 1). 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.
Ocenjevalni program
Lahko si preneseš izvorno kodo programa, s katerim bomo ocenjevali prejete rešitve: Rtk19Kolesarji.cpp.
Na voljo je tudi prevedena različica ocenjevalnega programa (za Windows).
Oblika vhodne datoteke
Pri tej nalogi so vsi testni primeri podani v eni vhodni datoteki. V prvi vrstici vhodne datoteke je niz z imenom naloge (Kolesarji), v drugi pa število testnih primerov (T). Sledijo testni primeri, pred vsakim od njih pa je še ena prazna vrstica.
Posamezni testni primer se začne z vrstico, ki vsebuje pet celih števil, ločenih s po enim presledkom: številka testnega primera (od 1 do T), število kolesarjev n (od 1 do 1000), število dirk d (od 1 do 1000), velikost navidezne ekipe k (od 1 do n) in m, t.j. največje število kolesarjev, ki jih smeš v navidezni ekipi zamenjati med dvema tekmama (od 1 do min(k, n − k)).
Sledi vrstica, ki vsebuje n celih števil, ločenih s po enim presledkom: to so t1, t2, …, tn. Zanje velja 1000 ≥ t1 ≥ t2 ≥ … ≥ tn ≥ 0.
Sledi d vrstic, ki po vrsti opisujejo izide vseh d dirk pri tem testnem primeru. Za vsako dirko je po ena vrstica, ki vsebuje številke kolesarjev (torej naravna števila od 1 do n) v takem vrstnem redu, v karkšnem so pri tej dirki prišli na cilj. Številke kolesarjev so ločene s po enim presledkom.
Primer: če bi imeli en sam testni primer, in sicer tistega z začetka tega opisa, bi bila vhodna datoteka takšna:
Kolesarji 1 1 5 3 3 1 100 80 60 40 30 5 3 2 4 1 3 4 5 1 2 1 2 5 3 4
V resnici bo pri tej nalogi 27 testnih primerov; za ilustracijo je tule prvih nekaj vrstic prave vhodne datoteke:
Kolesarji 27 1 5 8 3 1 100 80 60 40 20 2 1 3 4 5 ...
Če se bo zdelo potrebno (npr. ker bi bili rezultati preveč izenačeni), bomo do konca januarja dodali še kak testni primer.
Oblika izhodne datoteke
Oddaš lahko poljubno število izhodnih datotek s svojimi rešitvami. Pri tem vsaka izhodna datoteka vsebuje rešitve za enega ali več testnih primerov. Če za isti testni primer oddaš več rešitev, bomo pri ocenjevanju upoštevali najboljšo med njimi.
Oblika posamezne izhodne datoteke je naslednja:
V prvi vrstici naj bo koda, ki si jo dobil(a) ob registraciji in iz katere je razvidno, da si rešitev res poslal(a) ti, ne pa kdo drug. V drugi vrstici naj bo ime naloge (Kolesarji). Sledijo naj tvoje rešitve za enega ali več testnih primerov.
Vsaka rešitev se začne s prazno vrstico. Sledi naj d vrstic, ki za vsako dirko po vrsti opisujejo tvojo navidezno kolesarsko ekipo pred tisto dirko. Vsaka od teh vrstic naj vsebuje k števil (ločenih s po enim presledkom), ki povedo številke kolesarjev v tvoji navidezni ekipi. Kolesarje v ekipi lahko navedeš v poljubnem vrstnem redu. Rešitev je seveda veljavna le, če se dve zaporedni sestavi ekipe razlikujeta v največ m kolesarjih.
Primer: če bi bila naša uporabniška koda enaka 123456 in bi obstajal prvi testni primer, kakršen je prikazan zgoraj, bi lahko oddali spodnjo izhodno datoteko.
123456 Kolesarji 1 1 2 4 4 2 1 3 2 4
Ta rešitev je veljavna, ni pa najboljša možna (v resnici je pravzaprav najslabša možna).
Vhodni podatki
- kolesarji.in — datoteka z vsemi vhodnimi podatki za to nalogo.
- kolesarji-unix.in — ista datoteka, vendar z unixaškimi konci vrstic (LF namesto CRLF).
Registracija
Preden lahko oddajaš svoje rešitve, se prijavi prek spodnjega obrazca. Dodelili ti bomo enolično uporabniško kodo, ki jo boš potreboval(a) za pripravo svojih izhodnih datotek.
Opomba: pri tej nalogi lahko sodeluje kdorkoli, ne glede na starost, izobrazbo, itd. Objavili bomo rezultate vseh tekmovalcev, za morebitne praktične nagrade pa pridejo v poštev le srednješolci/ke in študentje/ke.