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

Volilna območja

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 18. marca 2016 (dan pred tekmovanjem).

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.

Primer: recimo, da imamo naslednjo mrežo velikosti 4 × 3 celic (številke v posameznih celicah pomenijo število prebivalcev).

3321
2270
3411

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

3321
2270
3411

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:

3321
2270
3411

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

Obrazec za oddajo rešitev

(Oddaja rešitev je možna do vključno 18. marca 2016.)

Datoteka s tvojo rešitvijo:

Najboljši doslej oddani razporedi

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
Rok Kralj2795
Matjaz Leonardis2423
Žan Ninin2292
Amon Stopinšek1795
Žiga Željko937
Dean Cerin476
Simon Gorše51
Nejc Kadivnik4

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