Fişierul intrare/ieşire:hacker.in, hacker.outSursăpreONI 2008 Runda 2
AutorMircea Bogdan PasoiAdăugată dedominoMircea Pasoi domino
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inhacker.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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content