Pracsiu Dan (dnprx) N dale. Dalele din tunel sunt numerotate începând cu 1, astfel încât, parcurgându-le linie cu linie și fiecare linie de la stânga la dreapta, se obține un șir strict crescător de numere naturale consecutive.
Sindbad se află la intrare, înaintea primei linii. Pentru a deschide poarta templului, el trebuie să ajungă pe dala numerotată cu P, călcând pe un număr minim de dale. Dacă există mai multe astfel de soluții, o va alege pe cea pentru care consumul total de picături de poțiune magică este minim.
Pe parcursul deplasării el trebuie să respecte următoarele reguli:
- de la intrare, poate sări pe orice dală aflată pe prima line, fără a consuma poțiune magică;
- de pe o dală numerotată cu
X, Sindbad poate sări fie pe dala numerotată cuX + 1, consumând o picătură de poțiune magică, fie pe dala numerotată cu2 * X, consumând două picături de poțiune magică.
Cerința
Scrieți un program care citește valorile N și P cu semnificația din enunț și rezolvă următoarele cerințe:
1. afișează numărul minim de dale pe care trebuie să calce pentru a deschide poarta;
2. afișează numărul natural T, reprezentând numărul minim de picături de poțiune magică necesare pentru deschiderea porții.
Date de intrare
Fișierul de intrare poarta.in conține pe prima linie un număr natural C reprezentând cerința din problemă care trebuie rezolvată (1 sau 2). Pe a doua linie se află numărul natural N, iar pe a treia linie se află numărul natural P cu semnificația din enunț.
Date de ieșire
Fișierul de ieșire poarta.out va conține o singură linie pe care va fi scris un număr natural reprezentând răspunsul la cerința C.
Restricții și precizări
2 ≤ N < 10.000Peste număr natural nenul cu cel mult1000de cifre; pentru o parte dintre teste, valorând în total 60 de puncte,Pare cel mult18cifre.- Recipientul conține o cantitate suficientă de poțiune magică.
- Pentru rezolvarea cerinței 1 se acordă maximum
60de puncte, iar pentru rezolvarea cerinței 2 se acordă maximum30de puncte. - În concurs s-au acordat
10puncte din oficiu. Aici se acordă pentru exemplele din enunț.
Exemplul 1:
poarta.in
1 5 9
poarta.out
3
Explicație
Tunelul are 5 dale pe fiecare linie. Sindbad trebuie să ajungă pe dala numerotată cu 9. Numărul minim de dale pe care trebuie să calce pentru a ajunge pe dala 9 pentru a deschide poarta este 3. De pe margine poate sări:
– pe dala numerotată cu 4 (consumă 0 picături de poțiune magică);
– de pe dala numerotată cu 4 pe cea numerotată cu 8 (consumă 2 picături de poțiune magică);
– de pe dala numerotată cu 8 pe cea numerotată cu 9 (consumă 1 picătură de poțiune magică).
Exemplul 2:
poarta.in
2 5 9
poarta.out
3
Explicație
Pentru a ajunge pe dala numerotată cu 9 are nevoie de cel puțin 3 picături de poțiune magică.