| Fişierul intrare/ieşire: | hacker.in, hacker.out | Sursă | preONI 2008 Runda 2 |
| Autor | Mircea Bogdan Pasoi | Adăugată de |  Mircea Pasoi •domino |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Hacker
Nargy vrea sa afle parola de la mail-ul lui Fumeanu ca sa ii faca o farsa. Dupa mai multe cercetari Nargy a aflat ca parola lui Fumeanu este un numar de N cifre in baza K care are urmatoarea proprietate: orice prefix de lungime i < N al numarului este diferit de sufixul corespunzator de lungime i. Mai mult de atat, Nargy stie si ce cifre se afla pe anumite pozitii din parola.
Nefiind un hacker prea priceput, singura metoda de a sparge o parola pe care o stie Nargy este brute force. Astfel, el ar vrea sa stie inainte, cate posibilitati exista pentru parola lui Fumeanu, folosind informatiile pe care le are pana acum.
Date de intrare
Fisierul de intrare hacker.in contine pe prima linie numerele N si K. Urmatoarea linie contine N caractere care pot fi numere intre 0 si K-1 sau caracterul ? pentru pozitiile din parola care nu se cunosc.
Date de iesire
In fisierul de iesire hacker.out se va afisa numarul de posiblitati pentru parola lui Fumeanu, modulo 666013.
Restrictii
- 1 ≤ N ≤ 200
- 2 ≤ K ≤ 10
- Numarul poate incepe cu cifra 0
Exemplu
| hacker.in | hacker.out |
|---|---|
| 4 2 1??0 | 3 |
Explicatie
Cele 3 parole posibile:
- 1000
- 1100
- 1110
1010 nu este o parola valida deoarece prefixul de lungime 2 (10) este egal cu sufixul de lungime 2 (10).
