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:

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

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

h2. Restricţii
* $4 < N,C < 200000$

* $1 < M ~i~ < 10, 1 < i < N$

* $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.$

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") ==