== include(page="template/taskheader" task_id="electoral") ==
Poveste şi cerinţă...
Frauda electorală este actul de a influenţa alegerile cu scopul de a compromite rezultatul unui proces democratic de alegere. Este ştiut că o cantitate mică de fraudă poate schimba rezultatul final al alegerilor. Fiind un demers ilegal, cel care fraudează doreşte să aducă un număr cât mai mic de modificări voturilor, pentru a-şi atinge scopul. În problema noastră, alegerile se desfăşoară în $N$ districte, în două etape:
*Etapa 1*: În fiecare district s-au numărat voturile exprimate şi s-a reţinut numărul de voturi pe care l-a primit orice candidat care a fost votat măcar o dată. Câştigător într-un district, în această etapă, este desemnat candidatul care a obţinut cel puţin $[V/2] + 1$ voturi, unde $V$ este numărul total de voturi exprimate în district. Dacă nu există un astfel de candidat, atunci acel district nu va fi luat în considerare la etapa $2$.
*Etapa 2*: Dintre câştigătorii rezultaţi după etapa $1$, este declarat câştigătorul alegerilor, acel candidat care a fost învingător în cel puţin $[K/2] + 1$ districte, unde $K$ este numărul districtelor care au avut câştigător în prima etapă. Scopul celui care doreşte să fraudeze alegerile este ca, după etapa $2$, să nu existe niciun câştigător al alegerilor. Această situaţie este posibilă dacă nu există niciun candidat care a învins în cel puţin $[K/2] + 1$ districte.
El încearcă să influenţeze alegerile în această direcţie, făcând un număr minim de modificări în etapa $1$.
O modificare constă în schimbarea oricărui vot din oricare district în favoarea oricărui alt candidat. Voturile nu pot fi transferate între districte iar numărul total de voturi exprimate în fiecare district rămâne acelaşi.
h2. Cerinţă
Se dau $N$ districte, $C$ candidaţi (numerotaţi cu valori din mulţimea $1,2,...,C$) şi, pentru fiecare district, numărul $M{~i~}$ de candidaţi care au primit voturi apoi cele $M{~i~}$ perechi de forma $candidat numărVoturiPrimite$ din acel district şi se cere:
# Determinarea câştigatorului alegerilor după etapa $2$, fără a se aduce modificări asupra voturilor înregistrate.
# Determinarea numărului minim de modificări ce trebuie aduse voturilor astfel încât după etapa $2$ să nu existe câştigător al alegerilor.
h2. Date de intrare
Fişierul de intrare $electoral.in$ ...
Fişierul de intrare $electoral.in$ conţine pe prima linie $T$, numărul cerinţei care va trebui rezolvată, $1$ sau $2$. Pe a doua linie se află două numere $N$ şi $C$, ce reprezintă numărul de districte şi numărul de candidaţi, separate printr-un spaţiu. Pe fiecare dintre următoarele $N$ linii se află, separate prin câte un spaţiu, un număr $M{~i~}$ urmat de $M{~i~}$ perechi de forma $candidat numarVoturiPrimite$.
h2. Date de ieşire
În fişierul de ieşire $electoral.out$ ...
Pentru cerinţa $1$, fişierul de ieşire $electoral.out$ va conţine câştigătorul alegerilor după etapa $2$, dacă nu se aduc modificări asupra voturilor. Pentru cerinţa $2$, fişierul $electoral.out$ va conţine numărul minim de modificări ce trebuie aduse voturilor în etapa $1$ pentru ca, după etapa $2$, să nu existe câştigător al alegerilor.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $4 < N,C < 200000$
* $1 < M{~i~} < 10, 1 < i < N$
* $1 < numărVoturiPrimite < 1.000.000$
* $În fiecare district, un candidat poate apărea în cel mult o pereche de forma candidat numărVoturiPrimite$
* $Se garantează existenţa unui câştigător după etapa 2.$
* $Pentru 20% dintre teste T=1 si pentru 80% dintre teste T=2.$
h2. Exemplu
table(example). |_. electoral.in |_. electoral.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1
5 4
2 3 2 2 4
2 4 2 1 1
3 2 3 4 1 3 1
4 2 1 1 1 4 1 3 1
1 2 1
| 2
|
h4. Explicaţie
Se rezolvă cerinţa $1$. Sunt $5$ districte şi $4$ candidaţi.
În primul district câştigă candidatul $2$ pentru că are $4$ voturi din $6$.
În al doilea district câştigă candidatul $4$ pentru că are $2$ voturi din $3$.
În al treilea district câştigă $2$ pentru că are $3$ voturi din $5$.
În al $4$-lea district nu există câştigător pentru că niciun candidat nu a întrunit $4/2+1$ voturi.
În al $5$-lea district $2$ este câştigător.
În total sunt $4$ districte din $5$ unde a existat câştigător, iar candidatul $2$ a câştigat în trei dintre acestea, deci câştigătorul alegerilor este candidatul $2$.
table(example). |_. electoral.in |_. electoral.out |
| 2
5 4
2 3 2 2 4
2 4 2 1 1
3 2 3 4 1 3 1
4 2 1 1 1 4 1 3 1
1 2 1
| 1
|
h3. Explicaţie
h4. Explicaţie
Se rezolvă cerinţa $2$.
O modificare posibilă este transferul unui vot dat candidatului $2$ în districtul $5$ către candidatul $4$ în acelaşi district. Asfel, în districtul $5$ va câştiga $4$ în etapa $1$ iar în etapa $2$ vor ajunge candidaţii: $2$, câştigător în $2$ districte $(1, 3)$ şi $4$, câştigător în $2$ districte $(2,5)$. În concluzie, după etapa $2$ nu există câştigător.
table(example). |_. electoral.in |_. electoral.out |
| 2
4 5
2 2 20 3 1
2 4 1 2 20
3 3 4 4 3 5 3
3 3 3 4 4 5 3
| 4
|
h4. Explicaţie
Se rezolvă cerinţa $2$.
În etapa $1$ observăm că $2$ iese câştigător în primele $2$ districte iar în districtele $3$ şi $4$ nu sunt câştigători. În concluzie, $2$ câştigă alegerile.
Numărul minim de modificări este $4$ şi o variantă de schimbări posibile este:
* în districtul $3$ schimbăm un vot de la candidatul $4$ şi unul de la candidatul $5$ către candidatul $3$ care va avea acum $6$ voturi din $10$ şi devine câştigător în etapa $1$.
* în districtul $4$ schimbăm două voturi de la candidatul $3$ la candidatul $4$ care va avea acum $6$ voturi din $10$ şi devine câştigător în etapa $1$.
Astfel, după etapa $1$, candidatul $2$ este câştigător în două districte iar candidaţii $3$ şi $4$ câştigă în câte un district. În concluzie, după aceste schimbări, nu există câştigător al alegerilor.
table(example). |_. electoral.in |_. electoral.out |
| 2
4 4
3 4 7 2 3 1 3
4 1 2 2 2 3 2 4 2
3 1 1 2 1 3 1
2 3 2 4 2
| 1
|
h4. Explicaţie
Se rezolvă cerinţa $2$.
În etapa $1$ observăm că $4$ iese câştigător în districtul $1$ cu $7$ voturi din $13$ iar în districtele $2, 3, 4$ nu este niciun câştigător în această etapă. În concluzie, $4$ este desemnat câştigător şi în etapa $2$.
Observăm că este necesară cel puţin o modificare pentru a nu avea niciun câştigător al alegerilor după etapa $2$. De exemplu, dacă schimbăm în districtul $1$ un vot de la candidatul $4$ către candidatul $2$, nu mai există câştigător în acest district în etapa $1$. Cum în celelate districte nu aveam câştigători, în final nu va mai fi desemnat niciun câştigător al alegerilor în etapa $2$.
...
== include(page="template/taskfooter" task_id="electoral") ==
