Rezolvare completă PbInfo #2977 poarta1

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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema poarta1:

#include <stdio.h>
int main()
{
    int i,k=1,ck,nv,j,v[1001],nk=0,gata=0,cer,pas=0,n,ok;
    int T=0;
    char c;
    FILE * f=fopen("poarta.in","r");
    FILE * g=fopen("poarta.out","w");
    fscanf(f,"%d %d", &cer, &n);
    nv=0;ok=0;
    while(!feof(f))
        {

            fscanf(f,"%c", &c);
            if(c>='0'&&c<='9')
            {
                v[++nv]=c-'0';
            }
        }
fclose(f);
    ck=n;
    while(ck)
    {
        nk++;ck=ck/10;
    }

    while(!gata)
    {
        j=0;k++;
        if(v[nv]%2==0)
            {
                T+=2;pas=2;
                for(i=1;i<=nv;i++)
                    {
                    j=j*10+v[i];
                    v[i]=j/2;j=j%2;

                    }
            }
        else
            {
                T++;pas=1;
                v[nv]--;
            }
        if(v[1]==0)
        {
            i=1;j=1;
            while(v[i]==0)i++;nv=nv-i+1;
            while(j<=nv)v[j++]=v[i++];
        }

        if(nv<=nk)
        {
            ck=0;
            for(i=1;i<=nv;i++) ck=ck*10+v[i];
            if(ck<=n)gata=1;
        }
    }
    if(pas==2&&ck*2==n+1){ck=n;T=T-1;}
    if(cer==1) fprintf(g,"%d\n",k);//ne minim de dale
            else fprintf(g,"%d\n",T);//nr minim de picaturi
    fclose(g);
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #2977 poarta1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2977 poarta1 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!