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
- Se garanteza ca toti gandacii au ADN-uri distincte doua cate doua.
- Din motive evolutionare, pentru 70% din teste se garanteaza ca oricum am alege un gandac cu ADN-ul X exista cel putin un alt gandac cu ADN-ul mutatie directa de-al lui X.
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 ADN-ul 1 1 1, care poate omora gandacii 1, 2 si 4
- Unul bazat pe ADN-ul 1 1 3, care poate omora gandacii 2, 3 si 5
