Revizia anterioară Revizia următoare
| 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 ...
Date de ieşire
În fişierul de ieşire electoral.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| electoral.in | electoral.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
