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 celor care votau Nicu arătau aşa:
| vot | frecventa |
|---|---|
| Gicu 1, Nicu 2 | 30 |
| Gicu 1, GVF 2, Nicu 3 | 1 |
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 susţinut practic de 64% din populatie la barajul cu GVF.
Totuşi înainte de a populariza şi mai mult 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 la 1 la m),
urmează 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.
Date de ieşire
În fişierul de ieşire stv.out trebuie sa afisati o permutare reprezentand ordinea candidatilor în alegeri. Castigatorul 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 |
| 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. După eliminarea candidatului 2, la al doilea pas candidatul 1 ramane cu 4 voturi şi candidatul 3 are 5 voturi -> e eliminat candidatul 1 şi 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).
