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 sa voteze la toate alegerile ce vor urma.În perioada post alegeri Arhirel contempleaza mult la rezultatele alegerilor şi la sistemul de vot.Lui Arhirel nu-i place deloc sistemul de alegeri dintr-un singur tur cu mai multi participanti.
Arhirel a descoperit un oraş cu 100 de votanţi unde existau 3 candidaţi “Geniul Viaductelor şi al Felinarelor” numit şi GVF, Nicu şi Gicu. Nicu şi Gicu au principii similare şi este de aşteptat ca votantii lui Nicu să-l prefere pe Gicu şi invers.
Totuşi rezultatul alegerilor în oraşul nostru a fost următorul:
GVF: 35
Nicu: 34
Gicu: 31
prin urmare GVF a fost declarat câştigător, cu toate că aproape 65% din votanţi ar fi votat cu Nicu în turul 2.
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 ordonarea candidaţilor după preferinţă:
În acest sistem candidaţii sunt eliminaţi unu cate unu pana ramane unu singur. La fiecare pas este eliminat candidatul care este favorit pe cele mai puţine liste.
Exemplu: dacă listele a 30 din cei care au votat Nicu arătau
Gicu 1, Nicu 2 (ei au decis sa nu pună GVF pe lista pe nici o poziţie)
Şi lista unuia dintre candidaţi arată Gicu 1, GVF 2, Nicu 3
La primul pas este eliminat Gicu care este preferat doar de 31 de votanţi. După aceea preferinţele devin:
Nicu: 34 + 30 = 64
GVF: 35 + 1 = 36
La pasul 2 e eliminat GVF şi castigator este Nicu sustinut practic de 64% din populatie la barajul cu GVF.
Totuşi înainte de a populariza şi mai mult sistemul Arhirel s-a decis sa-l testeze, cum Arhirel nu se pricepe prea bine sa centralizeze zeci de mii de voturi va cere ajutorul sa găsiţi ordinea candidatilor în nişte alegeri:
Input:
n - numărul de alegători
m - numărul de candidaţi (candidaţii vor avea numere de la 1 la m)
N linii de forma nr_i v_i_1, v_i_2, …., v_i_nr_i > numărul de candidaţi de pe lista alegătorului i, şi ordinea acestora pe lista.
Output:
O permutare reprezentand ordinea candidatilor în alegeri. Castigatorul fiind primul.
Date de intrare
Fişierul de intrare stv.in ...
Date de ieşire
În fişierul de ieşire stv.out ...
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 |
| stv1.in | stv1.out |
| 2 2 2 1 2 2 2 1 | 1 2 |
Explicaţie
In primul exemplu in primul pas candidatul 1 are 4 voturi, candidatul 2 are 2 voturi, candidatul 3 are 3 voturi. Dupa eliminarea canidatului 2, la al doilea pas canidatul 1 ramane cu 4 voturi si candidatul 3 are 5 voturi -> e eliminat candidatul 1 si castiga candidatul 3.
In cazul 2 la egalitate de voturi candidatul cu indicele cel mai mare este eliminat(prin urmare e eliminat 2, si 1 castiga).
