Fişierul intrare/ieşire:necromancer.in, necromancer.outSursăLot Seniori Alexandria, 2017, baraj 4
AutorStefania IonescuAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test0.4 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/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.innecromancer.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?