==Include(page="template/taskheader" task_id="stv")==
== include(page="template/taskheader" task_id="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, mai ales cele de saptamana viitoare.
În perioada pre şi 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 sunt prieteni şi au principii similare şi este de aşteptat ca votantii lui Nicu să-l prefere pe Gicu şi a lui Gicu pe Nicu în faţa celui de-al treilea candidat.
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ă probabil 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.
De discutat dacă datele le vrem citite normal sau generate după un sistem …
La fel şi discutii cu m şi n.
Nu scriu soluţii ca să le discutam...
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*':https://en.wikipedia.org/wiki/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). Voturile atribuite candidatului eliminat sunt redistribuite către următorul candidat încă în cursă (în ordinea listei de preferinţe). 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):
h2. Date de intrare
table(voturi Nicu). |_. # |_. 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.)
Datele de intrare se citesc din fisierul $stv.in$:
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*. Mai apoi, voturile $8$ şi $9$ vor fi 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. Clasamentul final va fi format din Ţicu (locul 1), urmat de Gicu (locul 2) şi, în final, de Nicu (locul 3).
* pe prima linie: un numar natural, $a$
* pe a doua linie: un numar natural, $b$
h2. Date de iesire
Totuşi, înainte de a populariza sistemul, Arhirel s-a decis să-l testeze si va cere ajutorul.
Datele de iesire se tiparesc in fisierul $stv.out$
h2. Date de intrare
* pe prima linie: cel mai mare divizor comun pentru $a$ si $b$. Daca $a$ si $b$ sunt numere prime intre ele, *atunci se va tipari 0*.
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$.
h2. Restrictii
h2. Date de ieşire
* Rezultatul nu va depasi niciodata valoarea 30000
Î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).
h2. Exemplu
h2. Restricţii
* $1 ≤ N, M ≤ 100$
h2. Exemplu
table(example). |_. stv.in |_. stv.out |
|8 12| 4 |
| 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
|
h3. Explicaţie
==Include(page="template/taskfooter" task_id="stv")==
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ă.
== include(page="template/taskfooter" task_id="stv") ==
