| Fişierul intrare/ieşire: | sprei.in, sprei.out | Sursă | IIOT 2019-20 Runda 1 |
| Autor | Tulba-Lecu Gabriel | Adăugată de |  Comisia IIOT 2019-20 •unibucPoli2019 |
| Timp execuţie pe test | 2.5 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | sprei.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
