Rezolvare PBinfo #1824

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.

• 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