1991 - Trepte 2 - Revision history

Mraa: /* Rezolvare */

2024-01-11T18:23:55Z

Rezolvare

← Older revision		Revision as of 18:23, 11 January 2024
Line 34:		Line 34:
	A treia: 1 -> 3 -> 4		A treia: 1 -> 3 -> 4
	==Rezolvare==		==Rezolvare==
	<syntaxhighlight lang="python3">		<syntaxhighlight lang="python3" line="1">
	def numar_moduri_urcare_trepte(n, k):		def numar_moduri_urcare_trepte(n, k):

Mraa at 17:25, 11 January 2024

2024-01-11T17:25:08Z

← Older revision		Revision as of 17:25, 11 January 2024
Line 34:		Line 34:
	A treia: 1 -> 3 -> 4		A treia: 1 -> 3 -> 4
	==Rezolvare==		==Rezolvare==
			<syntaxhighlight lang="python3">
	def numar_moduri_urcare_trepte(n, k):		def numar_moduri_urcare_trepte(n, k):
	~~mod = 9001~~

	# Inițializare vector dp		mod = 9001
	dp = [0] * (n + 1)		# Inițializare vector dp
	dp[1] = 1		dp = [0] * (n + 1)
			dp[1] = 1
			# Calcul numărul de moduri
			for i in range(1, n + 1):
			for j in range(1, k + 1):
			if i + j <= n:
			dp[i + j] = (dp[i + j] + dp[i]) % mod
			return dp[n]
			Citire date de intrare

	~~# Calcul numărul de moduri~~		n, k = map(int, input().split())
	~~for i in range~~(1, ~~n + 1~~):
	~~for j in range~~(~~1, k + 1~~):
	~~if i + j <= n:~~
	~~dp[i + j] = (dp[i + j] + dp[i]~~) ~~% mod~~

	~~return dp[n]~~		Calcul și afișare rezultat

	~~# Citire date de intrare~~
	~~n, k = map(int, input().split())~~

	~~# Calcul și afișare rezultat~~		result = numar_moduri_urcare_trepte(n, k) print(result)
	result = numar_moduri_urcare_trepte(n, k)		</syntaxhighlight>
	print(result)

Mraa: Pagină nouă: ==Cerința== O persoana are de urcat n trepte. Ştiind că de pe treapta i poate trece pe treapta i + 1, i + 2, ..., i + (k - 1) sau i + k, aflaţi în câte moduri poate urca cele n trepte. (inițial este pe treapta 1) ==Date de intrare== Programul citește de la tastatură numerele n și k. ==Date de ieșire== Programul va afișa pe ecran numărul c, reprezentând numărul de moduri în care poate urca cele n trepte. ==Restricții și precizări== 1 < n ≤ 100.000 1 ≤...

2023-12-11T15:59:40Z

Pagină nouă: ==Cerința== O persoana are de urcat n trepte. Ştiind că de pe treapta i poate trece pe treapta i + 1, i + 2, ..., i + (k - 1) sau i + k, aflaţi în câte moduri poate urca cele n trepte. (inițial este pe treapta 1) ==Date de intrare== Programul citește de la tastatură numerele n și k. ==Date de ieșire== Programul va afișa pe ecran numărul c, reprezentând numărul de moduri în care poate urca cele n trepte. ==Restricții și precizări== 1 < n ≤ 100.000 1 ≤...

New page

==Cerința==
O persoana are de urcat n trepte. Ştiind că de pe treapta i poate trece pe treapta i + 1, i + 2, ..., i + (k - 1) sau i + k, aflaţi în câte moduri poate urca cele n trepte. (inițial este pe treapta 1)

==Date de intrare==
Programul citește de la tastatură numerele n și k.

==Date de ieșire==
Programul va afișa pe ecran numărul c, reprezentând numărul de moduri în care poate urca cele n trepte.

==Restricții și precizări==
1 < n ≤ 100.000
1 ≤ k ≤ n - 1
deoarece numărul va fi prea mare sa va afișa modulo 9001.
==Exemplul 1==:
Intrare

2 2
Ieșire

1
Explicație
Există o soluție, aceea când sare direct pe treapta 2.

==Exemplul 2==:
Intrare

4 2
Ieșire

3
==Explicație==
Prima: 1 -> 2 -> 3 -> 4
A doua: 1 -> 2 -> 4
A treia: 1 -> 3 -> 4
==Rezolvare==
def numar_moduri_urcare_trepte(n, k):
mod = 9001

# Inițializare vector dp
dp = [0] * (n + 1)
dp[1] = 1

# Calcul numărul de moduri
for i in range(1, n + 1):
for j in range(1, k + 1):
if i + j <= n:
dp[i + j] = (dp[i + j] + dp[i]) % mod

return dp[n]

# Citire date de intrare
n, k = map(int, input().split())

# Calcul și afișare rezultat
result = numar_moduri_urcare_trepte(n, k)
print(result)