Vizualizare sursă pentru „0707 - Sum K”

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
<br>
== Explicatie ==
Sunt N=2 stagii, cu câte N=2 niveluri. Suma este K=2 pe fiecare stagiu.
<br>
Nivelurile sunt reprezentate de către coloanele matricelor.
<br>
Există 5 posibilități ca jocul să se termine cu succes.
== Exemplul 2 ==
; sumkin.txt
: 3 2
; sumkout.txt
: 28
<br>
== Explicatie == 
Sunt N=3 stagii, cu câte N=3 niveluri. Suma este K=2 pe fiecare stagiu.
<br>
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>