Alex a furat un calculator si incearca sa ii ghiceasca parola. Stie ca parola are o lungime N si este formata din caractere dintr-un alfabet cu L simboluri (de exemplu, literele mici ale alfabetului englez, pentru care L=26). De fiecare data cand introduce o parola gresita, sistemul ii spune daca parola adevarata este mai mica sau mai mare lexicografic decat cea introdusa.
Daca Alex cauta parola in mod optim (folosind o strategie de cautare binara asupra celor L^N parole posibile, ordonate lexicografic), care este numarul minim de incercari suficient pentru a gasi cu certitudine parola, in cel mai rau caz?
- Date de intrare
- Se citesc pe o singura linie doua numere intregi L si N, separate printr-un spatiu: dimensiunea alfabetului, respectiv lungimea parolei.
- Date de iesire
- Se afiseaza un singur numar intreg: numarul minim de incercari necesare, in cel mai rau caz, pentru a gasi parola printr-o cautare binara optima asupra celor L^N parole posibile.
- Restrictii
- 2 <= L <= 30 1 <= N <= 12 L^N <= 4 * 10^18 (astfel incat numarul de parole posibile sa incapa pe 64 de biti)
Exemple
Exemplul 1
Intrare
26 10
Iesire
48
Exemplul 2
Intrare
2 1
Iesire
1