Rezolvare completă PbInfo #1824 Pitic

Enunt

Carmen, piticul de gradina vrea sa meargă în vizita la piticul Tulosba. Pentru a ajunge la Tulosba, Carmen trebuie sa meargă printr-o rețea de N galerii, fiecare alcătuită din M sectoare.

Rețeaua poate fi reprezentată printr-un tablou cu N linii, numerotate de la 1 la N și M coloane, numerotate de la 1 la M . Carmen ocupă sectorul 1 al galeriei 1. Tulosba ocupă sectorul M al galeriei 1.

La galeria n se termina rețeaua și începe gradina unde sunt niște copii răi care vor sa-l spargă pe Carmen cu bâtele de Baseball.

Dacă sectorul curent a lui Carmen este (i,j), atunci se poate deplasa:

  • La dreapta, ajungând în sectorul (i,j+1) .
  • Pe diagonala la dreapta în sus, ajungând în sectorul (i-1,j+1).
  • Pe diagonala la dreapta în jos, ajungând în sectorul (i+1,j+1).

Cerința

Sa se afișeze în câte moduri poate Carmen sa ajungă la Tulosba.

Date de intrare

Fișierul de intrare pitic.in conține pe prima linie numerele n și m cu semnificația din problema.

Date de ieșire

Fișierul de ieșire pitic.out va conține pe prima linie numărul S, reprezentând în câte moduri poate sa ajungă Carmen la Tulosba.

Restricții și precizări

  • Carmen nu poate sa coboare sub nivelul 1
  • Carmen nu poate sa urce mai sus de nivelul n pentru ca o sa fie spart de copii
  • 1 ≤ n ≤ 43
  • 1 ≤ m ≤ 43

Exemplu

pitic.in

3 3

pitic.out

2

pitic.in

7 1

pitic.out

1

pitic.in

4 4

pitic.out

4

Explicație

Exemplul 1 : Piticul Carmen poate sa meargă de 2 ori la dreapta sau o dată pe diagonala în sus la dreapta și odată pe diagonala în jos la dreapta.

Exemplul 2 : Piticul Carmen poate sa meargă doar la dreapta deoarece dacă urca pe nivelul 2 o sa ajungă în gradina.

Exemplul 3 :
  • Modul 1: Dreapta de 3 ori
  • Modul 2: Diagonala sus, Diagonala jos, Dreapta
  • Modul 3: Diagonala sus, Dreapta , Diagonala jos
  • Modul 4: Dreapta, Diagonala sus, Diagonala jos

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

/** O sa tinem matricea invers . Nivelul 1 o sa fie coloana 1 ,
iar distanta 1 o sa fie linia 1. Aplicam programare dinamica , avand grija sa
nu iesim din matrice sau sa adaugam un sa 2 ori acelasi lucru.
Raspunsul o sa se afle in casuta a[1][m] */

#include <iostream>
#include <fstream>

using namespace std;

ifstream in("pitic.in");
ofstream out("pitic.out");
const int NMAX = 43;
long long int a[NMAX+1][NMAX+1];

int main()
{
    long long int n,i,j,m;
    in>>n;
    in>>m;
    a[1][1]=1; /// Pot ajunge in pozitia initiala doar intr-un mod
    for(j=1; j<=m; j++)
    {
        for(int i=1; i<=n; i++)
        {
            /// a[i][j] Reprezinta modurile in care pot ajunge la nivelul 1, distanta j
            if(i!=1)
                a[i][j]+=a[i-1][j-1]; /// Diagonala dreapta sus
            if(j!=1)
                a[i][j]+=a[i][j-1]; /// Dreapta
            if(i!=n)
                a[i][j]+=a[i+1][j-1]; /// Diagonala dreapta jos
        }
    }
    out<<a[1][m];
}

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 #1824 Pitic

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