Srednješolsko tekmovanje ACM iz računalništva in informatike
Volilna območja
Podroben opis naloge
Dana je karirasta mreža, ki predstavlja površino neke države. Za vsako celico (kvadratek) mreže je znano, koliko prebivalcev živi na njej. Naloga je razdeliti mrežo na določeno število volilnih območij tako, da so si volilna območja čim bolj podobna po številu prebivalcev. Natančneje povedano, radi bi, da bi bila razlika v številu prebivalcev med območjem z največ prebivalci in območjem z najmanj prebivalci čim manjša.
Vsaka celica mreže mora v celoti pripadati natanko enemu volilnemu območju. Vsako volilno območje mora biti sestavljeno iz ene ali več celic mreže. Pri tem volilno območje ne sme biti iz več nepovezanih delov — njegove celice se morajo „držati skupaj“ v enem kosu. Natančneje lahko to povemo takole: rekli bomo, da sta dve celici sosednji, če imata skupno eno od stranic (ne pa, če imata skupno le eno od oglišč). Za volilno območje mora veljati, da lahko iz katere koli njegove celice dosežemo katero koli drugo njegovo celico tako, da se na vsakem koraku premaknemo iz trenutne celice v eno od njenih sosed in da nikoli ne stopimo ven iz tega območja.
Primer: recimo, da imamo naslednjo mrežo velikosti 4 × 3 celic (števila v posameznih celicah pomenijo število prebivalcev).
| 3 | 3 | 2 | 1 |
| 2 | 2 | 7 | 0 |
| 3 | 4 | 1 | 1 |
Recimo, da moramo mrežo razdeliti na 3 volilna območja. Ena možnost je naslednja (vsako od treh območij je prikazano s svojo barvo):
| 3 | 3 | 2 | 1 |
| 2 | 2 | 7 | 0 |
| 3 | 4 | 1 | 1 |
Pri tej razdelitvi imamo eno območje (rdeče) s 3 + 3 + 2 + 1 = 9 prebivalci, eno območje (zeleno) z 2 + 2 + 7 + 0 = 11 prebivalci in eno območje (modro) s 3 + 4 + 1 + 1 = 9 prebivalci. Razlika med območjem z največ in območjem z najmanj prebivalci je torej 11 − 9 = 2.
Isto mrežo lahko razdelimo na tri območja tudi takole:
| 3 | 3 | 2 | 1 |
| 2 | 2 | 7 | 0 |
| 3 | 4 | 1 | 1 |
Pri tej razdelitvi ima rdeče območje 10 prebivalcev, zeleno 9 prebivalcev, modro pa 10 prebivalcev. Razlika med območjem z največ in območjem z najmanj prebivalci je tako 10 − 9 = 1, zato je ta rešitev boljša od prejšnje (pri kateri je bila ta razlika 2).
Kot vidimo že iz tega primera, smejo biti območja različnih oblik in velikosti.
Opomba: če bi se slučajno zgodilo, da bi veliko tekmovalcev oddajalo enako dobre rešitve, bomo zgornji ocenjevalni kriterij (razliko med območjem z največ in območjem z najmanj prebivalci) zamenjali s kakšnim drugim (na primer vsoto kvadratov odstopanj od povprečnega števila prebivalcev na območje).
Ocenjevalni program
Lahko si preneseš izvorno kodo programa, s katerim bomo ocenjevali prejete rešitve: Rtk16Gerry.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 (Gerrymandering), v drugi pa število testnih primerov (N). Sledijo testni primeri, pred vsakim od njih pa je še ena prazna vrstica.
Posamezni testni primer se začne z vrstico, ki vsebuje štiri cela števila, ločena s po enim presledkom: najprej številka testnega primera (od 1 do N), nato w, nato h in nato še d. Pri tem pomeni w širino mreže, h njeno višino, d pa zahtevano število volilnih območij pri tem testnem primeru. Veljalo bo 1 ≤ w ≤ 300, 1 ≤ h ≤ 300 in 1 ≤ d ≤ w · h. Sledi še h vrstic, v vsaki od njih pa je po w celih števil, ločenih s po enim presledkom; ta števila po vrsti podajajo število prebivalcev v posameznih celicah mreže. Število prebivalcev v posamezni celici je vsaj 0 in največ 106, v celi mreži pa je skupaj največ 2 · 109 prebivalcev.
Primer: če bi imeli en sam testni primer, in sicer tistega z gornje slike, bi bila vhodna datoteka takšna:
Gerrymandering 1 1 4 3 3 3 3 2 1 2 2 7 0 3 4 1 1
V resnici bo pri tej nalogi 300 testnih primerov; za ilustracijo je tule prvih nekaj vrstic prave vhodne datoteke:
Gerrymandering 300 1 95 30 53 1153 1124 1116 1079 1149 1155 1145 1098 1120 ... ...
Oblika izhodne datoteke
Oddaš lahko poljubno število izhodnih datotek s svojimi razbitji vhodnih mrež na volilna območja. 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 (Gerrymandering). Sledijo naj tvoje rešitve za enega ali več testnih primerov.
Vsaka rešitev se začne s prazno vrstico. V drugi vrstici naj bo številka testnega primera, na katerega se nanaša ta rešitev. Sledi naj h vrstic, ki opisujejo tvoje razbitje mreže pri tem testnem primeru. Vsaka od teh vrstic naj vsebuje w nenegativnih celih števil, ločenih s presledkom, ki za posamezna polja povedo, kateremu volilnemu območju pripada tisto polje.
Pri tem je vseeno, kako oštevilčiš volilna območja; celo ni nujno, da po vrsti uporabljaš števila od 0 naprej (morajo pa biti vsa uporabljena števila manjša od 109). Dopustno je celo, da isto številko uporabiš za več volilnih območij. Omejitev je le ta, da če v tvojem razporedu dve volilni območji mejita eno na drugo (imata kakšen skupen rob), potem ne smeta imeti iste številke. Poleg tega mora seveda za vsako volilno območje veljati, da imajo vsa polja, ki jih to območje pokriva, isto številko. Število različnih (nepraznih) volilnih območij pri tvoji razdelitvi mora biti enako d (torej številu območij, ki ga zahteva ta testni primer).
Primer: če bi bila naša uporabniška koda enaka 123456 in bi obstajal prvi testni primer, kakršen je prikazan na gornji sliki, bi lahko oddali spodnjo izhodno datoteko.
123456 Gerrymandering 1 9 9 9 2 5 9 2 2 5 5 2 2
To ustreza drugi rešitvi iz zgornjih primerov; razlika med območjem z največ in tistim z najmanj prebivalci je 1.
Vhodni podatki
- gerry.in — datoteka z vsemi vhodnimi podatki za to nalogo (16 MB).
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.