Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | stv.in, stv.out | Sursă | FMI No Stress 10 |
| Autor | Marius Dumitran | Adăugată de |  FMI No Stress 9 •fminostress9 |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Stv
Balaurul Arhirel a început sa fie pasionat de alegeri. El a realizat ca alegerile sunt foarte importante şi şi-a propus să voteze la toate alegerile ce vor urma. În perioada post-alegeri Arhirel reflectă mult asupra rezultatelor alegerilor şi la sisteme de vot. Lui Arhirel nu-i place deloc sistemul de alegeri dintr-un singur tur cu mai multi participanţi.
După perioade lungi de contemplare Arhirel a ajuns la concluzia ca ar fi super dacă s-ar putea implementa sistemul Single Transferable Vote . Sistemul permite ca un cetăţean să îşi ordoneze candidaţii după preferinţă. După ce toate preferinţele sunt exprimate, candidaţii sunt eliminaţi unul câte unul (până când ramâne unul singur). La fiecare pas este eliminat candidatul care este favorit pe cele mai puţine liste (în caz de egalitate, este eliminat cel cu indicele cel mai mare). Ordinea în care sunt eliminaţi candidaţii determină clasamentul final al alegerilor.
De exemplu, să presupunem că există 3 candidaţi şi s-au înregistrat 9 voturi, iar buletinele de vot arată astfel (numele votanţilor este omis, pentru a păstra anonimitatea votului):
| # | Gicu | Nicu | Ţicu |
|---|---|---|---|
| 1 | 1 | 2 | 3 |
| 2 | 1 | 2 | 3 |
| 3 | 1 | 2 | 3 |
| 4 | 1 | 2 | 3 |
| 5 | - | 2 | 1 |
| 6 | - | 2 | 1 |
| 7 | - | 2 | 1 |
| 8 | 3 | 1 | 2 |
| 9 | - | 1 | 2 |
(candidatul marcat cu numărul 1 este considerat favorit, urmat de cel marcat cu numărul 2, ş.a.m.d.)
La primul pas este eliminat Nicu care este favorit doar pentru 2 din cei 9 votanţi (voturile 8 şi 9). El este eliminat din listele tuturor alegătorilor. Astfel, voturile 8 şi 9 vor fi mai apoi redistribuite către al doilea candidat în ordinea preferinţelor (dacă acesta există). Astfel, Ţicu va ajunge să primească în total 5 voturi (voturile 5, 6, 7, 8, 9), care îi vor asigura victoria împotriva lui Gicu. Astfel, clasamentul final va fi format din Ţicu (locul 1), urmat de Gicu (locul 2) şi, în final, de Nicu (locul 3).
Totuşi, înainte de a populariza sistemul, Arhirel s-a decis să-l testeze si va cere ajutorul.
Date de intrare
Fisierul de intrare stv.in contine pe prima linie N - numărul de alegători şi M - numărul de candidaţi (candidaţii vor avea numere de ordine de la 1 la M),
urmează N linii de forma c[i] numărul de candidaţi de pe lista alegătorului i, urmat de c[i] numere naturale distincte din intervalul 1..N, reprezentând candidaţii aleşi în ordinea preferinţelor cetăţeanului i.
Date de ieşire
În fişierul de ieşire stv.out trebuie să afişaţi o permutare, reprezentând clasamentul candidaţilor în urma alegerior (câştigatorul fiind primul).
Restricţii
- 1 ≤ N, M ≤ 100
Exemplu
| stv.in | stv.out |
|---|---|
| 9 3 3 1 2 3 3 1 2 3 3 1 2 3 3 1 2 3 2 3 2 2 3 2 2 3 2 3 2 3 1 2 2 3 | 3 1 2 |
| 2 2 2 1 2 2 2 1 | 1 2 |
Explicaţie
Primul exemplu este identic cu cel explicat în enunţ. Candidatul 1 este Gicu, candidatul 2 este Nicu, iar candidatul 3 este Ţicu.
In exemplul 2, la egalitate de voturi, candidatul cu indicele cel mai mare este eliminat; prin urmare este eliminat candidatul 2, iar candidatul 1 câştigă.
