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 * 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: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 * 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.000
• P este număr natural nenul cu cel mult 1000 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.
• În concurs s-au acordat 10 puncte 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ă.

#include <bits/stdc++.h>

using namespace std;

ifstream cin("poarta.in");
ofstream cout("poarta.out");

int cer , n , a[10001] , cnt = 1 , b;
string p;

void scadere(int a[] , int &n)
{
    int i = 1;
    while(a[i] == 0)
    {
        a[i] = 9;
        i++;
    }
    a[i] -= 1;
    if(a[n] == 0) n--;
}

void impartire(int a[] , int &n)
{
    int r = 0;
    for(int i = n ; i >= 1 ; i--)
    {
        int c = r * 10 + a[i];
        a[i] = c / 2;
        r = c % 2;
    }
    if(a[n] == 0) n--;
}

int maimare(int a[] , int n , int x)
{
    if(n > 4) return 1;
    else
    {
        int y = 0;
        for(int i = n ; i >= 1 ; i--)
            y = y * 10 + a[i];
        return y > x;
    }
}
int main()
{
    cin >> cer >> n >> p;
    int k = p.length();
    for(int i = 0 ; i < k ; i++)
        a[k - i] = p[i] - '0';
    while(maimare(a , k , n))
        if(a[1] %2 == 1 || !maimare(a , k , n + 1))
        {
            scadere(a , k);
            cnt++;
            b++;
        }
        else
        {
            impartire(a , k);
            cnt++;
            b += 2;
        }
    if(cer == 1) cout << cnt;
    else cout << b;
        return 0;
}