Diferente pentru problema/primar intre reviziile #16 si #39

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="primar") ==
Dubluveu a fost ales de curand primar in "Popricani":http://ro.wikipedia.org/wiki/Comuna_Popricani%2C_Ia%C5%9Fi. Ca sa poate obtine "fondurile structurale":http://www.fonduri-structurale.ro pentru dezvoltarea comunei, proaspatul primar trebuie sa-si aleaga cat mai repede consilierii locali. Pentru ca in campania electorala, le-a promis popricanenilor ca nu va face discrimanari (ca si primarul precedent). Astfe, pentru a-si alege Consiliul Local va trebui sa respecte urmatoarele:
Dubluveu a fost ales de curand primar in "Popricani":http://ro.wikipedia.org/wiki/Comuna_Popricani%2C_Ia%C5%9Fi. Ca sa poate obtine "fondurile structurale":http://www.fonduri-structurale.ro 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:
* sa aiba $N$ angajati
* sa angajeze atat barbati, cat si femei
* valoarea discriminarii de pe fiecare "ulite":http://dexonline.ro/search.php?cuv=ulita sa fie minima, unde valoarea minima pentru o ulita reprezinta diferenta dintre numarul de barbati si numarul de femei alesi in Consiliul Local de pe acea ulita.
 
Privit de sus, comuna are o retea de ulite paralela cu axele de coordonate ale sistemului XoY (reprezentate formal de niste segmente). De-alungul acestor drumuri sunt construite $N$ case (reprezentate formal de niste puncte), ca in figura:
* 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.
!problema/primar?grid.jpg!
_Liniile rosii reprezinta ulite, pe cand liniile albastre reprezinta case ce nu se afla pe aceeasi ulita. Spre exemplu casele 1, 2 si 3 sunt pe aceeasi ulita. De asemenea, casele 4, 5 si 6 sunt pe aceeasi ulita. In schimb, casele 1 si 5_ +sunt pe ulite diferite+.
_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+.
h2. 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. Valoarea discriminarii pe o ulita este numeric egala cu diferenta dintre numarul de barbati si numarul de femei, alesi in Consiliul Local, care isi au domiciliul pe acea ulita.
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+.
h2. Date de intrare
h2. Restrictii
* $1 ≤ N ≤ 300 000$
* $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$
* $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
h2. Exemplu
h3. Explicatie
din casele 2, 3 si, respectiv, 5 casa vei alege cate un barbat, iar din casele 1 si 4 vei alege cate o femeie.
din casele 2, 3 si, respectiv, 5 vei alege cate un barbat, iar din casele 1 si 4 vei alege cate o femeie.
!problema/primar?ex.jpg!
== include(page="template/taskfooter" task_id="primar") ==
 
 
 

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
2639