Sindbad a descoperit un recipient care conține o poțiune magică și o inscripție care descrie cum se poate deschide poarta unui templu. Urmând instrucțiunile din inscripție, Sindbad a ajuns la un tunel acoperit cu dale pătrate, aliniate astfel încât formează linii și coloane. Tunelul are mai multe linii, iar pe fiecare linie sunt câte dale. Dalele din tunel sunt numerotate începând cu , 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 , 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 , Sindbad poate sări fie pe dala numerotată cu , consumând o picătură de poțiune magică, fie pe dala numerotată cu , consumând două picături de poțiune magică.
Cerință
Scrieți un program care citește valorile și cu semnificația din enunț și rezolvă următoarele cerințe:
- afișează numărul minim de dale pe care trebuie să calce pentru a deschide poarta;
- afișează numărul natural , 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 reprezentând cerința din problemă care trebuie rezolvată ( sau ). Pe a doua linie se află numărul natural , iar pe a treia linie se află numărul natural 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 .
Restricții și precizări
- ;
- este număr natural nenul cu cel mult de cifre; pentru o parte dintre teste, valorând în total de puncte, are cel mult cifre.
- Recipientul conține o cantitate suficientă de poțiune magică.
- Pentru rezolvarea cerinței se acordă maximum de puncte, iar pentru rezolvarea cerinței se acordă maximum de puncte.
Exemplul 1
poarta.in
1
5
9
poarta.out
3
Explicație
Tunelul are dale pe fiecare linie. Sindbad trebuie să ajungă pe dala numerotată cu . Numărul minim de dale pe care trebuie să calce pentru a ajunge pe dala pentru a deschide poarta este . De pe margine poate sări:
- pe dala numerotată cu (consumă 0 picături de poțiune magică);
- de pe dala numerotată cu pe cea numerotată cu (consumă picături de poțiune magică);
- de pe dala numerotată cu pe cea numerotată cu (consumă 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 are nevoie de cel puțin picături de poțiune magică.