Revizia anterioară Revizia următoare
| 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 omoare cat mai repede toti cei N gandaci ce i-au infestat casa.
Un gandac poate fi reprezentat prin ADN-ul sau - un vector de numere naturale de lungime M cu valori de la 1 la B.
Pentru a se adapta mediului, gandacii urmeaza mai multe mutatii, o mutatie luand harta ADN a unui gandac si crescand sau scazand exact o pozitie cu 1 (nu poate creste daca este B si nu poate scadea daca este 1).
Paul stie ADN-ul tuturor gandacilor si stie ca poate creea pentru un anumit ADN X un sprai care omoara toti gandacii cu ADN-ul X sau o mutatie directa de-al lui X.
Cerinta
Paul vrea sa stie care este numarul minim de sprai-uri necesare pentru a omori toti gandacii.
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 ADN-ul fiecarui gandac.
Date de ieşire
Pe prima linie a fisierului sprei.out afisati numarul minim de spreiuri necesare pentru a omora toti gandacii.
Restricţii
- 1 ≤ N ≤ 10.000
- 1 ≤ B ≤ 109
- 1 ≤ M ≤ 100
- NU se garanteza ca toti gandacii au ADN diferit
- Din motive evolutionare, pentru 70% din teste se garanteaza ca oricum am alege doua ADN-uri X si Y apartinand unor gandaci, exista un sir de ADN-uri A 1 A 2 ... A k $ astfel incat $A 1 = X, A k = Y, $A i+1 $ este o mutatie directa a lui $A i $ si $A i $ apare in lista de ADN-uri.
Exemplu
| sprei.in | sprei.out |
|---|---|
| 5 3 3 1 1 1 1 1 2 1 1 3 1 2 1 1 2 3 | 2 |
Explicaţie
Alegem doua tuburi de sprei:
- Unul bazat pe harta ADN 1 1 1, care o sa poate omora gandacii 1, 2 si 4
- Unul bazat
