Fişierul intrare/ieşire:	electoral.in, electoral.out	Sursă	Concursul Naţional de Informatică Urmaşii lui Moisil 2017
Autor	Netedu Andrei	Adăugată de	Andrici Cezar •andrici_cezar
Timp execuţie pe test	0.5 sec	Limită de memorie	128000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Electoral

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.

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:

1. Determinarea câştigatorului alegerilor după etapa 2, fără a se aduce modificări asupra voturilor înregistrate.
2. 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.

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.

Date de ieşire

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.

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.

Exemplu

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.

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.

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.

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.

Cum se trimit solutii?