Sprei

Paul are o problema mare cu gandacii in casa, el trebuie sa omoare cat mai repede cele $N$ colonii gandaci ce i-au infestat casa.

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 poate fi 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 (exista o unica pozitie in vectorul lor de pozitie si este de exact 1), acestia isi construiesc un wormhole intre cele doua colonii.

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 wormholurile dintre colonii.
Pentru asta, el poate achizitiona spreiuri speciale, cu un sprei putand dezactiva toate wormholurile plecand dintr-o colonie.

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$.

h2. Cerinta

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

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

h2. Date de intrare

h2. Date de ieşire

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

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

h2. Restricţii

h3. Explicaţie

Alegem doua tuburi de sprei:

Cumparam doua tuburi de sprei:

* Unul bazat pe pozitia $1 1 1$
* Unul bazat pe pozitia $1 1 2$

* Un sprei de tipul $1$
* Un sprei de tipul $3$

== include(page="template/taskfooter" task_id="sprei") ==