| Fişierul intrare/ieşire: | primar.in, primar.out | Sursă | Winter Challenge 2008, Runda 1 |
| Autor | Bogdan Alexandru Stoica | Adăugată de |  Bogdan-Alexandru Stoica •fireatmyself |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Primar
Dubluveu a fost ales de curand primar in Popricani. Ca sa poate obtine fondurile structurale pentru dezvoltarea comunei, proaspatul ales trebuie sa-si desemenze cat mai repede consilierii locali. Pentru ca in campania electorala, le-a promis popricanenilor ca nu va face discrimanari (ca si primarul precedent), va trebui sa respecte urmatoarele norme:
- Cosiliul Local trebuie sa aiba N angajati (cate un singur angajat din fiecare casa, din cele N ale comunei)
- va trebui sa angajeze atat barbati, cat si femei
- valoarea totala a discriminarii sa fie minima.
Putem considera comuna ca un plan cartezian, unde casele sunt reprezentate de puncte, iar ulitele sunt reprezentate de dreptele paralele cu axele de coordonate, pe care se alfa cel putin o casa (vezi figura). Discriminarea pe o astfel de ulita este egala cu diferenta (in modul) dintre numarul de barbati si numarul de femei alesi in Consiliul Local. Discriminarea totala este suma discriminarilor de pe fiecare ulita.
Liniile rosii reprezinta ulite, pe cand liniile albastre unesc case ce nu se afla pe aceeasi ulita. Spre exemplu casele 1, 2, 3 si 4 sunt pe aceeasi ulita. De asemenea, casele 5, 6 si 7 sunt pe aceeasi ulita. In schimb, casele 1 si 5 sunt pe ulite diferite, deoarece dreapta care trece prin punctele 1 si 5 nu este paralela nici cu OX nici cu OY. Pentru a intelege si mai bine desenul, putem spune ca doua case sunt pe aceeasi ulita daca si numai daca au aceeasi abscisa sau aceeasi ordonata.
Cerinta
In calitate de sef de campanie al primarului Dubluveu, trebuie sa determini o alegere a celor N consilieri, care sa respecte promisiunile facute popricanenilor si care sa aiba o discriminare totala minima.
Date de intrare
Pe prima linie a fisierului de intrare primar.in se afla numarul N. Pe urmatoarele N linii se afla coordonatele caselor.
Date de iesire
In fisierul de iesire primar.out veti afisa, pe prima linie, discriminarea minima obtinuta, iar pe ce-a de-a doua, un sir de N numere din multimea {0,1}. Astfel, al i-lea numar va reprezenta alegerea facuta de tine pentru a i-a casa din fisierul de intrare. (0 - reprezinta ca ai numit un barbat de la casa i, 1 - reprezinta ca ai numit o femeie de la casa i)
Restrictii
- 1 ≤ N ≤ 131 072
- coordonatele caselor sunt numere intregi ale caror coordonate nu depasesc, in modul, 2 000 000 000
- daca o ulita are doar o singura casa atunci, indiferent de alegerea facuta, discriminarea pe acea ulita va fi 0.
- intr-o casa locuiesc cel putin un barbat si cel putin o femeie
- nu exista doua case la aceeasi coordonata
- veti primi 40% din punctaj pentru determinarea corecta a discriminarii minime si 100% daca raspundeti corect la intreaga cerinta
Exemplu
| primar.in | primar.out |
|---|---|
| 5 0 0 0 1 1 0 1 1 1 2 | 1 1 0 0 1 0 |
Explicatie
din casele 2, 3 si, respectiv, 5 vei alege cate un barbat, iar din casele 1 si 4 vei alege cate o femeie.
Pe ulitele 1, 2 si 4, diferenta dintre numarul de barbati (punctele albastre) si numarul de femei (punctele rosii) este 0. Pe ulita 3, diferenta este 1. In total discriminarea are valoarea 1, fiind minima posibila pe acest exemplu.
Daca se considera ulita paralela cu OX care trece prin punctul de coordonate (1,2) se observa ca aceasta nu mai trece prin niciun alt punct dat in fisierul de intrare. Prin urmare dicriminarea pe ulita 5 va fi 0. Chiar daca ai fi ales ca din acea casa sa angajezi o femeie, discriminarea de pe ulita 5 ar fi ramasa tot 0, in schimb ar fi crescut discriminarea de pe ulita 3 si, totodata, discriminarea totala.
