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

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

#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")