Editing 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")
python pitic.py