Oros Ioana Diana at 06:46, 18 May 2024

2024-05-18T06:46:23Z

← Older revision		Revision as of 06:46, 18 May 2024
Line 8:		Line 8:

	= Date de ieşire =		= Date de ieşire =
	Fişierul de ieşire <code>scaraOUT.txt</code> va conţine pe prima linie o valoare care reprezintă numărul cerut.		Fişierul de ieşire <code>scaraOUT.txt</code> va conţine pe prima linie o valoare care reprezintă numărul cerut. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

	= Restricţii şi precizări =		= Restricţii şi precizări =

Oros Ioana Diana at 06:46, 18 May 2024

2024-05-18T06:46:10Z

Show changes

Oros Ioana Diana: Pagină nouă: Claudia vrea să construiască o scară cu N trepte astfel încât prima treaptă să fie la înălţimea 0 şi ultima treaptă să fie la înălţimea H. Fiind pusă pe glume, ea îi cere arhitectului să proiecteze o scară neobişnuită, în care treptele sunt dispuse astfel încât, la un moment dat, să poţi urca, coborî sau rămâne la acelaşi nivel. Pentru a fi uşor de urcat sau coborât, valoarea absolută a diferenţei dintre înălţimile la care se află oricar...

2024-01-08T23:39:28Z

Pagină nouă: Claudia vrea să construiască o scară cu N trepte astfel încât prima treaptă să fie la înălţimea 0 şi ultima treaptă să fie la înălţimea H. Fiind pusă pe glume, ea îi cere arhitectului să proiecteze o scară neobişnuită, în care treptele sunt dispuse astfel încât, la un moment dat, să poţi urca, coborî sau rămâne la acelaşi nivel. Pentru a fi uşor de urcat sau coborât, valoarea absolută a diferenţei dintre înălţimile la care se află oricar...

New page

Claudia vrea să construiască o scară cu N trepte astfel încât prima treaptă să fie la înălţimea 0 şi ultima treaptă să fie la înălţimea H. Fiind pusă pe glume, ea îi cere arhitectului să proiecteze o scară neobişnuită, în care treptele sunt dispuse astfel încât, la un moment dat, să poţi urca, coborî sau rămâne la acelaşi nivel. Pentru a fi uşor de urcat sau coborât, valoarea absolută a diferenţei dintre înălţimile la care se află oricare două trepte consecutive trebuie să fie mai mică sau egală cu o valoare dată, K. Nicio treaptă nu se poate afla la o înălţime negativă sau la o înălţime mai mare decât H.
== Cerința ==
Scrieţi un program care să determine numărul de scări diferite cu N trepte, ce pot fi construite respectând cerinţele Claudiei. Deoarece numărul de scări poate fi foarte mare, determinaţi restul împărţirii acestui număr la 666013.
== Date de intrare ==
Pe prima linie a fişierului scarain.txt se află numerele naturale N H K, separate prin câte un spaţiu, cu semnificaţia din enunţ.
== Date de ieșire ==
Fişierul de ieşire scaraout.txt va conţine pe prima linie o valoare care reprezintă numărul cerut.
== Restricții și precizări ==
*1 ≤ N ≤ 109
*1 ≤ H ≤ 100
*1 ≤ K ≤ H
*Pentru un număr de teste în valoare de 30 de puncte, N ≤ 20.000 şi H ≤ 20
*Pentru un număr de teste în valoare de 50 de puncte, N ≤ 500.000 şi H ≤ 30
*Pentru un număr de teste în valoare de 80 de puncte, H ≤ 30
== Exemplul 1 ==
; scarain.txt
: 4 3 2
; scaraout.txt
: 8
<br>
== Exemplul 2 ==
; scarain.txt
: 5 4 2
; scaraout.txt
: 34
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#0149 - Scara
def count_stairs(N, H, K):
mod = 666013
dp = [[0] * (H + 1) for _ in range(N + 1)]

# Inițializăm cazurile de bază
dp[0][0] = 1

# Calculăm numărul de modalități folosind programarea dinamică
for i in range(1, N + 1):
for j in range(1, H + 1):
dp[i][j] = sum(dp[i - 1][max(0, j - K + 1):j]) % mod

return sum(dp[N]) % mod

# Citirea datelor de intrare
with open("scarain.txt", "r") as infile:
N, H, K = map(int, infile.readline().split())

# Verificarea restricțiilor
if not (1 <= N <= 10**9 and 1 <= H <= 100 and 1 <= K <= H):
print("Fals")
else:
# Calculul rezultatului
result = count_stairs(N, H, K)

# Scrierea rezultatului în fișierul de ieșire
with open("scaraout.txt", "w") as outfile:
outfile.write(str(result))

</syntaxhighlight>

== Explicatie ==
0 0 1 3
0 2 3 3
0 1 2 3
0 1 3 3
0 2 1 3
0 0 2 3
0 1 1 3
0 2 2 3

0149 - Scara - Revision history

Oros Ioana Diana at 06:46, 18 May 2024

Oros Ioana Diana at 06:46, 18 May 2024