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

Rezolvare

def numar_moduri(n, m):

   dp = [[0] * (m + 1) for _ in range(n + 1)]
   # Inițializăm prima coloană cu 1, deoarece Carmen poate să ajungă în oricare dintre cele n niveluri pornind de la nivelul 1
   for i in range(1, n + 1):
       dp[i][1] = 1
   # Calculăm numărul total de moduri
   for j in range(2, m + 1):
       for i in range(1, n + 1):
           dp[i][j] = dp[i][j - 1]  # Carmen merge la dreapta
           if i - 1 > 0:
               dp[i][j] += dp[i - 1][j - 1]  # Carmen merge pe diagonala sus
           if i + 1 <= n:
               dp[i][j] += dp[i + 1][j - 1]  # Carmen merge pe diagonala jos
   return sum(dp[i][m] for i in range(1, n + 1))

if __name__ == "__main__":

   with open("pitic.in", "r") as f:
       n, m = map(int, f.readline().split())
   rezultat = numar_moduri(n, m)
   with open("pitic.out", "w") as g:
       g.write(str(rezultat) + "\n")