| Fişierul intrare/ieşire: | necromancer.in, necromancer.out | Sursă | Lot Seniori Alexandria, 2017, baraj 4 |
| Autor | Stefania Ionescu | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Necromancer
În urbea X au avut loc alegeri la care au participat K candidaţi. Fiecare cetăţean din cei N ai urbei s-a prezentat la scrutin şi a scris o permutare p1, p2, ..., pK pe buletinul de vot, reprezentând lista candidaţilor în ordinea preferinţelor cetăţeanului. Va câştiga alegerile candidatul care se află de cele mai multe ori pe poziţia 1 în cele N permutări introduse în urna de vot.
Necromancerul doreşte să câştige candidatul cu numărul 1, Charles. În acest scop, el a reuşit să afle, pentru fiecare votant i din cei N, câte un şir Ai care este subşir al permutării i introduse în urna de vot. Necromancerul poate apoi să creeze, prin mijloace numai de el ştiute, voturi suplimentare pentru candidatul 1.
Ştiindu-se, pentru fiecare permutare i din urnă, câte un subşir Ai al acesteia, se cere să se determine care este numărul minim de voturi suplimentare care trebuie create de Necromancer pentru ca să existe cel puţin un set valid de voturi în care câştigă candidatul 1, ajutat desigur şi de voturile suplimentare. Un set de voturi este valid dacă, pentru fiecare cetăţean i este aleasă o permutare care conţine şirul Ai ca subşir.
Date de intrare
Fişierul necromancer.in va conţine pe prima linie două numere naturale N şi K cu semnificaţia din enunţ. Pe următoarele N linii se află subşirurile celor N permutări, ştiute de Necromancer. Linia i+1 va conţine un număr întreg Li, reprezentând lungimea subşirului. Apoi, linia i+1 va mai conţine Li numere naturale reprezentând elementele subşirului.
Date de ieşire
Fişierul necromancer.out va conţine pe singura linie un număr natural V reprezentând numărul minim de voturi suplimentare necesare pentru a exista cel puţin un set valid de voturi în care candidatul 1 câştigă.
Restricţii şi precizări
- 1 ≤ N, K ≤ 1 000
- Pentru 30% din teste, 1 ≤ N, K ≤ 100
- Pentru 60% din teste, 1 ≤ N, K ≤ 500
- Candidatul 1 trebuie să aibă strict mai multe voturi ca următorul clasat pentru a câştiga.
Exemplu
| necromancer.in | necromancer.out |
|---|---|
| 3 4 2 3 1 3 2 1 3 4 1 2 3 4 | 1 |
Explicaţie
Putem alege permutările:
3 2 1 4
2 1 3 4
1 2 3 4
În această situaţie, candidaţii 1, 2 şi 3 au fiecare 1 vot. Astfel, Necromancerul mai are nevoie să adauge un singur vot suplimentar pentru ca 1 să aibă două voturi şi să câştige.
Observăm că am putea alege neconvenabil permutările:
2 3 4 1
2 1 3 4
1 2 3 4
În acest caz, candidatul 2 ar fi avut 2 voturi şi candidatul 1 doar 1 vot. Astfel, Necromancerul ar fi trebuit să adauge 2 voturi suplimentare.
