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 harta ADN-ul sau - un cuvant de lungime M in baza B.
Paul stie reprezentarile hartilor tuturor gandacilor si stie ca poate creea pentru o anumita harta ADN X un sprai care poate sa omoare toti gandacii cu o harta ADN Y cu proprietatea ca X si Y difera in maxim o pozitie c, si |X c - Y c | <= 1.
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 0 si B-1 care reprezinta harta ADN a 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
Exemplu
| sprei.in | sprei.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
