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