1824 - Pitic - Revision history

Mraa: /* Rezolvare */

2024-01-11T18:27:56Z

Rezolvare

← Older revision		Revision as of 18:27, 11 January 2024
Line 54:		Line 54:
	Modul 4: Dreapta, Diagonala sus, Diagonala jos		Modul 4: Dreapta, Diagonala sus, Diagonala jos
	==Rezolvare==		==Rezolvare==
	<syntaxhighlight lang="python3">		<syntaxhighlight lang="python3" line="1">
	def numar_moduri(n, m):		def numar_moduri(n, m):

Mraa at 17:33, 11 January 2024

2024-01-11T17:33:23Z

← Older revision		Revision as of 17:33, 11 January 2024
Line 54:		Line 54:
	Modul 4: Dreapta, Diagonala sus, Diagonala jos		Modul 4: Dreapta, Diagonala sus, Diagonala jos
	==Rezolvare==		==Rezolvare==
			<syntaxhighlight lang="python3">
	def numar_moduri(n, m):		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		dp = [[0] * (m + 1) for _ in range(n + 1)]
	for i in range(1, 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
	dp[i][1] = 1		for i in range(1, n + 1):
			dp[i][1] = 1
	# Calculăm numărul total de moduri		# Calculăm numărul total de moduri
	for j in range(2, m + 1):		for j in range(2, m + 1):
	for i in range(1, n + 1):		for i in range(1, n + 1):
	dp[i][j] = dp[i][j - 1] # Carmen merge la dreapta		dp[i][j] = dp[i][j - 1] # Carmen merge la dreapta
	if i - 1 > 0:		if i - 1 > 0:
	dp[i][j] += dp[i - 1][j - 1] # Carmen merge pe diagonala sus		dp[i][j] += dp[i - 1][j - 1] # Carmen merge pe diagonala sus
	if i + 1 <= n:		if i + 1 <= n:
	dp[i][j] += dp[i + 1][j - 1] # Carmen merge pe diagonala jos		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))
	return sum(dp[i][m] for i in range(1, n + 1))

	if __name__ == "__main__":		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:		with open("pitic.in", "r") as f:
	g.write(str(rezultat) + "\n")		n, m = map(int, f.readline().split())
	~~python pitic.py~~		rezultat = numar_moduri(n, m)
			with open("pitic.out", "w") as g:
			g.write(str(rezultat) + "\n")
			</syntaxhighlight>

Mraa: Pagină nouă: ==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șt...

2023-12-21T20:57:19Z

Pagină nouă: ==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șt...

New page

==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