Cerinţa

Alice s-a pierdut din nou în labirint. Labirintul este de forma unui triunghi dreptunghic împărțit în camere organizate pe linii și coloane. Pe prima linie este o singură cameră, pe a doua sunt două camere, etc. Pe ultima linie sunt n camere. Din fiecare cameră se poate merge în camerele situate pe linia următoare și pe aceeași coloană, sau pe coloane cu 1 mai mari sau mai mici decât coloana curentă, dar fără să se părăsească labirintul. Astfel din camera (i,j) se poate merge în camerele (i+1,j-1), (i+1,j) și (i+1,j+1), dacă acestea există. Alice se află în camera de pe prima linia și de pe prima coloana (1,1).

Ca să iasă din labirint, Alice trebuie să ajungă într-o cameră de pe ultima linie. Calculați și afișați numărul de trasee pe care poate Alice să iasă din labirint.

Date de intrare

Fișierul de intrare alice_xi.in conține pe prima linie numărul n, reprezentând numărul de linii din labirint.

Date de ieşire

Fişierul de ieşire alice_xi.out va conţine pe prima linie numărul s, reprezentând numărul de trasee pe care poate Alice să iasă din labirint.

Restricţii şi precizări

1 ≤ n ≤ 35

Exemplu

alice_xi.in

alice_xi.out

Explicație

Pe ultima linie sunt 3 camere. În prima se poate ajunge în 2 moduri, în cea de-a doua în 2 noduri, iar în a treia într-un singur mod. În total sunt 5 moduri în care se poate ajunge pe ultima linie.

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 Alice_XI:

#include <fstream>
using namespace std;
ifstream fin("alice_xi.in");
ofstream fout("alice_xi.out");
int main()
{
    long long A[101][101],c=0;
    int n;
    fin>>n;
    A[1][1]=1;
    for(int i=2;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(j==1) A[i][j]=A[i-1][j]+A[i-1][j+1];
            else if(j==i-1) A[i][j]=A[i-1][j-1]+A[i-1][j];
                 else if(j==i) A[i][j]=A[i-1][j-1];
                      else A[i][j]=A[i-1][j-1]+A[i-1][j]+A[i-1][j+1];
    for(int i=1;i<=n;i++)
        c=c+A[n][i];
    fout<<c;
    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 #3258 Alice_XI

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3258 Alice_XI 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!

Rezolvare completă PbInfo #3258 Alice_XI