Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2020-12-19 17:04:19.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:stv.in, stv.outSursăFMI No Stress 10
AutorMarius DumitranAdăugată defminostress9FMI No Stress 9 fminostress9
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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 sisteme 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 unul câte unul până când ramane unul singur. La fiecare pas este eliminat candidatul care este favorit pe cele mai puţine liste (in caz de egalitate este eliminat cel cu indicele cel mai mare).
Exemplu: dacă listele celor care votau Gicu arătau aşa:

votfrecventa
Gicu 1, Nicu 230
Gicu 1, GVF 2, Nicu 31

La primul pas este eliminat Gicu care este preferat doar de 31 de votanţi. El este eliminat din listele tuturor alegătorilor. 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] numărul de candidaţi de pe lista alegătorului i, urmata de nr[i] numere in ordinea acestora pe lista sa.

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.instv.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
stv.instv.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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?