Fişierul intrare/ieşire:sprei.in, sprei.outSursăIIOT 2019-20 Runda 1
AutorTulba-Lecu GabrielAdăugată deunibucPoli2019Comisia IIOT 2019-20 unibucPoli2019
Timp execuţie pe test2.5 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sprei

Sprei

Paul are o problema mare cu gandacii in casa, el trebuie sa nimiceasca cat mai repede cele N colonii gandaci ce i-au infestat casa.
Fiind o persoana abstracta, acesta traieste intr-un cub M dimensional, in care fiecare pozitie poate fi codificata printr-un vector A 1, A 2 ... A M cu valori intre 0 si B - 1.

O colonie de gandaci este reprezentata prin pozitia sa - un vector de numere naturale de lungime M cu valori de la 0 la B - 1.
Fiind entitati sociale, gandacii incearca sa isi uneasca coloniile. Asftel, daca doua colonii ocupa pozitii adiatente in casa lui Paul (pozitia uneia se obtine adaugand sau scand 1 din pozitia celeilalte), acestia isi construiesc un tunel intre cele doua colonii.

Paul stie pozitiile celor N colonii, si doreste sa blocheze toate tunelurile din ele.
Pentru asta, el poate achizitiona spreiuri speciale.
Exista N tipuri de sprei, sprei-ul de tip i distrugand toate tunelurile avand unul dintre cele doua capete colonia i.

Cerinta

Paul vrea sa stie care este numarul minim de sprai-uri necesare pentru a bloca toate tunelurile.

Date de intrare

Pe prima linie a fisierului sprei.in se dau N, M, B.
Pe urmatoarele N linii urmeaza cate M numere intre 1 si B care reprezinta pozitia fiecarei colonii.

Date de ieşire

Pe prima linie a fisierului sprei.out afisati numarul minim de spreiuri necesare pentru a bloca toate tunelurile.

Restricţii

  • 1 ≤ N ≤ 10.000
  • 1 ≤ B ≤ 109
  • 1 ≤ M ≤ 100
  • Se garanteza ca toate coloniile au pozitii distincte doua cate doua.
  • Pentru teste in valoare de 30 de puncte 1 ≤ N ≤ 10

Exemplu

sprei.insprei.out
5 3 4
1 1 1
1 1 2
1 1 3
1 2 1
1 2 3
2

Explicaţie

Cumparam doua tuburi de sprei:

  • Un sprei de tipul 1
  • Un sprei de tipul 3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?