poarta

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 $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ă cu $X + 1$, consumând o picătură de poțiune magică, fie pe dala numerotată cu $2 \cdot X$, consumând două picături de poțiune magică.

Cerință

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 \leq N < 10 \ 000$;
• $P$ este număr natural nenul cu cel mult $1 \ 000$ de cifre; pentru o parte dintre teste, valorând în total $60$ de puncte, $P$ are cel mult $18$ cifre.
• Recipientul conține o cantitate suficientă de poțiune magică.
• Pentru rezolvarea cerinței $1$ se acordă maximum $60$ de puncte, iar pentru rezolvarea cerinței $2$ se acordă maximum $30$ de puncte.

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ă.