3084 - Cub Dinamic - Revision history

Mraa: /* Rezolvare */

2024-01-11T18:29:14Z

Rezolvare

← Older revision		Revision as of 18:29, 11 January 2024
Line 45:		Line 45:
	fără a trece prin camere blocate.		fără a trece prin camere blocate.
	==Rezolvare==		==Rezolvare==
	<syntaxhighlight lang="python3">		<syntaxhighlight lang="python3" line="1">
	MOD = 1234567		MOD = 1234567

Mraa at 17:35, 11 January 2024

2024-01-11T17:35:10Z

← Older revision		Revision as of 17:35, 11 January 2024
Line 45:		Line 45:
	fără a trece prin camere blocate.		fără a trece prin camere blocate.
	==Rezolvare==		==Rezolvare==
			<syntaxhighlight lang="python3">
	MOD = 1234567		MOD = 1234567

	def numar_moduri(n, m, camere_blocate):		def numar_moduri(n, m, camere_blocate):
	~~dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]~~

	# Inițializăm matricea cu 0-uri		dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
	for i in range(n + 1):		# Inițializăm matricea cu 0-uri
	for j in range(n + 1):		for i in range(n + 1):
	for k in range(n + 1):		for j in range(n + 1):
	dp[i][j][k] = 0		for k in range(n + 1):
			dp[i][j][k] = 0
	# Marcam camerele blocate cu -1		# Marcam camerele blocate cu -1
	for i, j, k in camere_blocate:		for i, j, k in camere_blocate:
	dp[i][j][k] = -1		dp[i][j][k] = -1
			# Dacă camera finală este blocată sau camera de plecare este blocată, returnăm 0
	# Dacă camera finală este blocată sau camera de plecare este blocată, returnăm 0		if dp[1][1][1] == -1 or dp[n][n][n] == -1:
	if dp[1][1][1] == -1 or dp[n][n][n] == -1:		return 0
	return 0		dp[1][1][1] = 1
			for i in range(1, n + 1):
	dp[1][1][1] = 1		for j in range(1, n + 1):
			for k in range(1, n + 1):
	for i in range(1, n + 1):		# Dacă camera este blocată, continuăm
	for j in range(1, n + 1):		if dp[i][j][k] == -1:
	for k in range(1, n + 1):		continue
	# Dacă camera este blocată, continuăm		# Actualizăm modul în care putem ajunge în camerele adiacente
	if dp[i][j][k] == -1:		if i + 1 <= n and dp[i + 1][j][k] != -1:
	continue		dp[i + 1][j][k] = (dp[i + 1][j][k] + dp[i][j][k]) % MOD
			if j + 1 <= n and dp[i][j + 1][k] != -1:
	# Actualizăm modul în care putem ajunge în camerele adiacente		dp[i][j + 1][k] = (dp[i][j + 1][k] + dp[i][j][k]) % MOD
	if i + 1 <= n and dp[i + 1][j][k] != -1:		if k + 1 <= n and dp[i][j][k + 1] != -1:
	dp[i + 1][j][k] = (dp[i + 1][j][k] + dp[i][j][k]) % MOD		dp[i][j][k + 1] = (dp[i][j][k + 1] + dp[i][j][k]) % MOD
	if j + 1 <= n and dp[i][j + 1][k] != -1:		return dp[n][n][n]
	dp[i][j + 1][k] = (dp[i][j + 1][k] + dp[i][j][k]) % MOD
	if k + 1 <= n and dp[i][j][k + 1] != -1:
	dp[i][j][k + 1] = (dp[i][j][k + 1] + dp[i][j][k]) % MOD

	return dp[n][n][n]

	if __name__ == "__main__":		if __name__ == "__main__":
	~~with open("cub_dinamic.in", "r") as f:~~
	~~n, m = map(int, f.readline().split())~~
	~~camere_blocate = [tuple(map(int, f.readline().split())) for _ in range(m)]~~

	~~rezultat = numar_moduri(n, m, camere_blocate)~~

	with open("cub_dinamic.out", "w") as g:		with open("cub_dinamic.in", "r") as f:
	g.write(str(rezultat) + "\n")		n, m = map(int, f.readline().split())
	~~python cub_dinamic.py~~		camere_blocate = [tuple(map(int, f.readline().split())) for _ in range(m)]
			rezultat = numar_moduri(n, m, camere_blocate)
			with open("cub_dinamic.out", "w") as g:
			g.write(str(rezultat) + "\n")
			</syntaxhighlight>

Mraa: Pagină nouă: ==Cerința== Se dă un tablou tridimensional, de dimensiune n x n x n , fiecare element reprezentând o camera. m dintre acestea sunt blocate și nu pot fi traversate. Dintr-o cameră având coordonatele (i,j,k) te poți deplasa in camerele de coordonate (i+1,j,k) , (i,j+1,k) și (i,j,k+1) . Știind că pornești din camera cu coordonate (1,1,1) , se cere să se afișeze numărul de moduri modulo 1234567 de a ajunge in camera de coordonate (n,n,n,) . ==Date de intrare...

2023-12-21T21:04:48Z

Pagină nouă: ==Cerința== Se dă un tablou tridimensional, de dimensiune n x n x n , fiecare element reprezentând o camera. m dintre acestea sunt blocate și nu pot fi traversate. Dintr-o cameră având coordonatele (i,j,k) te poți deplasa in camerele de coordonate (i+1,j,k) , (i,j+1,k) și (i,j,k+1) . Știind că pornești din camera cu coordonate (1,1,1) , se cere să se afișeze numărul de moduri modulo 1234567 de a ajunge in camera de coordonate (n,n,n,) . ==Date de intrare...

New page

==Cerința==
Se dă un tablou tridimensional, de dimensiune n
x n
x n
, fiecare element reprezentând o camera. m
dintre acestea sunt blocate și nu pot fi traversate. Dintr-o cameră având coordonatele (i,j,k)
te poți deplasa in camerele de coordonate (i+1,j,k)
, (i,j+1,k)
și (i,j,k+1)
.

Știind că pornești din camera cu coordonate (1,1,1)
, se cere să se afișeze numărul de moduri modulo 1234567
de a ajunge in camera de coordonate (n,n,n,)
.

==Date de intrare==
Fișierul de intrare cub_dinamic.in conține pe prima linie numerele n și m, iar pe următoarele m linii câte 3 numere reprezentând coordonatele camerelor blocate.

==Date de ieșire==
Fișierul de ieșire cub_dinamic.out va conține pe prima linie numărul S, reprezentând numărul de moduri modulo 1234567
de a ajunge din camera (1,1,1)
în camera (n,n,n)
.

==Restricții și precizări==
1 ≤ n ≤ 200
1 ≤ coordonatele camerelor ≤ n
0 ≤ m ≤ n*n*n
Dacă nu se poate ajunge in camera (n,n,n)
sau una dintre camerele (1,1,1)
sau (n,n,n)
este blocată, atunci se va afișa 0.
==Exemplu==:
cub_dinamic.in

3 1
2 2 2
cub_dinamic.out

54
==Explicație==
Există 54 de moduri de a ajunge din camera (1,1,1)
în camera (n,n,n)
fără a trece prin camere blocate.
==Rezolvare==
MOD = 1234567

def numar_moduri(n, m, camere_blocate):
dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]

# Inițializăm matricea cu 0-uri
for i in range(n + 1):
for j in range(n + 1):
for k in range(n + 1):
dp[i][j][k] = 0

# Marcam camerele blocate cu -1
for i, j, k in camere_blocate:
dp[i][j][k] = -1

# Dacă camera finală este blocată sau camera de plecare este blocată, returnăm 0
if dp[1][1][1] == -1 or dp[n][n][n] == -1:
return 0

dp[1][1][1] = 1

for i in range(1, n + 1):
for j in range(1, n + 1):
for k in range(1, n + 1):
# Dacă camera este blocată, continuăm
if dp[i][j][k] == -1:
continue

# Actualizăm modul în care putem ajunge în camerele adiacente
if i + 1 <= n and dp[i + 1][j][k] != -1:
dp[i + 1][j][k] = (dp[i + 1][j][k] + dp[i][j][k]) % MOD
if j + 1 <= n and dp[i][j + 1][k] != -1:
dp[i][j + 1][k] = (dp[i][j + 1][k] + dp[i][j][k]) % MOD
if k + 1 <= n and dp[i][j][k + 1] != -1:
dp[i][j][k + 1] = (dp[i][j][k + 1] + dp[i][j][k]) % MOD

return dp[n][n][n]

if __name__ == "__main__":
with open("cub_dinamic.in", "r") as f:
n, m = map(int, f.readline().split())
camere_blocate = [tuple(map(int, f.readline().split())) for _ in range(m)]

rezultat = numar_moduri(n, m, camere_blocate)

with open("cub_dinamic.out", "w") as g:
g.write(str(rezultat) + "\n")
python cub_dinamic.py