poarta

Time limit: 0.1s Memory limit: 8MB Input: poarta.in Output: poarta.outPoints by default: 10p

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 NN dale. Dalele din tunel sunt numerotate începând cu 11, 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 PP, 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 XX, Sindbad poate sări fie pe dala numerotată cu X+1X + 1, consumând o picătură de poțiune magică, fie pe dala numerotată cu 2X2 \cdot X, consumând două picături de poțiune magică.

Cerință

Scrieți un program care citește valorile NN și PP 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 TT, 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 CC reprezentând cerința din problemă care trebuie rezolvată (11 sau 22). Pe a doua linie se află numărul natural NN, iar pe a treia linie se află numărul natural PP 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 CC.

Restricții și precizări

  • 2N<10 0002 \leq N < 10 \ 000;
  • PP este număr natural nenul cu cel mult 1 0001 \ 000 de cifre; pentru o parte dintre teste, valorând în total 6060 de puncte, PP are cel mult 1818 cifre.
  • Recipientul conține o cantitate suficientă de poțiune magică.
  • Pentru rezolvarea cerinței 11 se acordă maximum 6060 de puncte, iar pentru rezolvarea cerinței 22 se acordă maximum 3030 de puncte.

Exemplul 1

poarta.in

1
5
9

poarta.out

3

Explicație

Tunelul are 55 dale pe fiecare linie. Sindbad trebuie să ajungă pe dala numerotată cu 99. Numărul minim de dale pe care trebuie să calce pentru a ajunge pe dala 99 pentru a deschide poarta este 33. De pe margine poate sări:

  • pe dala numerotată cu 44 (consumă 0 picături de poțiune magică);
  • de pe dala numerotată cu 44 pe cea numerotată cu 88 (consumă 22 picături de poțiune magică);
  • de pe dala numerotată cu 88 pe cea numerotată cu 99 (consumă 11 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 99 are nevoie de cel puțin 33 picături de poțiune magică.

Log in or sign up to be able to send submissions!