Oros Ioana Diana at 07:08, 18 May 2024

2024-05-18T07:08:26Z

Oros Ioana Diana: Pagină nouă: sumk este un joc de perspicacitate, cu N stagii numerotate de la 1 la N. Un joc se termină cu succes dacă jucătorul a parcurs în ordine, de la 1 la N, toate cele N stagii ale jocului şi în fiecare stagiu a obţinut exact K puncte. Fiecare stagiu are N niveluri, numerotate de asemenea de la 1 la N. Jucătorul are posibilitatea să câştige 0, 1, …, K puncte pe oricare nivel al stagiului curent. Dacă jucătorul se găseşte în stagiul i pe nivelul j și numărul tot...

2024-01-08T23:20:49Z

Pagină nouă: sumk este un joc de perspicacitate, cu N stagii numerotate de la 1 la N. Un joc se termină cu succes dacă jucătorul a parcurs în ordine, de la 1 la N, toate cele N stagii ale jocului şi în fiecare stagiu a obţinut exact K puncte. Fiecare stagiu are N niveluri, numerotate de asemenea de la 1 la N. Jucătorul are posibilitatea să câştige 0, 1, …, K puncte pe oricare nivel al stagiului curent. Dacă jucătorul se găseşte în stagiul i pe nivelul j și numărul tot...

New page

sumk este un joc de perspicacitate, cu N stagii numerotate de la 1 la N. Un joc se termină cu succes dacă jucătorul a parcurs în ordine, de la 1 la N, toate cele N stagii ale jocului şi în fiecare stagiu a obţinut exact K puncte. Fiecare stagiu are N niveluri, numerotate de asemenea de la 1 la N. Jucătorul are posibilitatea să câştige 0, 1, …, K puncte pe oricare nivel al stagiului curent.

Dacă jucătorul se găseşte în stagiul i pe nivelul j și numărul total de puncte obţinute până în acel moment în acest stagiu este mai mic decât K, el va trece în mod obligatoriu pe nivelul j+1 al stagiului i. Dacă jucătorul primește cel puţin un punct pe nivelul j și astfel punctajul său în stagiul i devine exact K, atunci jucătorul trece în mod automat pe nivelul j al stagiului i+1 sau termină jocul cu succes dacă i=N.
== Cerința ==
Cunoscând numărul N de stagii ale jocului şi numărul K de puncte care trebuie să fie obţinute în fiecare stagiu, să se determine numărul de posibilităţi modulo 578537 pentru ca jocul să se termine cu succes.
== Date de intrare ==
Fișierul de intrare sumkin.txt conține pe prima linie două numere naturale N K cu semnificația descrisă anterior.
== Date de ieșire ==
Fișierul de ieșire sumkout.txt va conține pe prima linie un singur număr natural P reprezentând numărul total de posibilităţi modulo 578537 pentru ca jocul să se termine cu succes.
== Restricții și precizări ==
*1 ≤ K ≤ N ≤ 500
*Fie x punctajul final într-un stagiu oarecare. Atunci dacă x ≠ K, jocul se termină cu eșec.
*Pentru 20% din teste, K ≤ N ≤ 10, iar pentru 30% din teste, K≤N≤100
== Exemplul 1 ==
; sumkin.txt
: 2 2
; sumkout.txt
: 5
 
== Explicatie ==
Sunt N=2 stagii, cu câte N=2 niveluri. Suma este K=2 pe fiecare stagiu.
 
Nivelurile sunt reprezentate de către coloanele matricelor.
 
Există 5 posibilități ca jocul să se termine cu succes.
== Exemplul 2 ==
; sumkin.txt
: 3 2
; sumkout.txt
: 28
 
== Explicatie ==
Sunt N=3 stagii, cu câte N=3 niveluri. Suma este K=2 pe fiecare stagiu.
 
Sunt reprezentate doar câteva dintre cele 28 de posibilități.
== Rezolvare ==
<syntaxhighlight lang="python" line>
#0707 - Sum K
def numar_posibilitati(N, K):
MOD = 578537

if not (1 <= K <= N <= 500):
print("Fals")
exit()

# Inițializare matrice dp cu zero-uri
dp = [[0] * (K + 1) for _ in range(N + 1)]

# Caz de bază: dp[i][0] = 1 pentru orice i
for i in range(N + 1):
dp[i][0] = 1

# Calculul dinamic pentru numărul de posibilități
for i in range(1, N + 1):
for j in range(1, K + 1):
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD

return dp[N][K]

# Citirea datelor de intrare din fișierul "sumkin.txt"
try:
with open("sumkin.txt", "r") as file:
N, K = map(int, file.readline().split())
except Exception as e:
print("Fals")
exit()

# Calculul rezultatului și afișarea acestuia în fișierul "sumkout.txt"
result = numar_posibilitati(N, K)

with open("sumkout.txt", "w") as file:
file.write(str(result) + "\n")

</syntaxhighlight>

0707 - Sum K - Revision history

Oros Ioana Diana at 07:08, 18 May 2024