View source for 0707 - Sum K

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

Dacă jucătorul se găseşte în stagiul <code>i</code> pe nivelul <code>j</code> și numărul total de puncte obţinute până în acel moment în acest stagiu este mai mic decât <code>K</code>, el va trece în mod obligatoriu pe nivelul <code>j+1</code> al stagiului <code>i</code>. Dacă jucătorul primește cel puţin un punct pe nivelul <code>j</code> și astfel punctajul său în stagiul <code>i</code> devine exact <code>K</code>, atunci jucătorul trece în mod automat pe nivelul <code>j</code> al stagiului <code>i+1</code> sau termină jocul cu succes dacă <code>i=N</code>.

= Cerința =
Cunoscând numărul <code>N</code> de stagii ale jocului şi numărul <code>K</code> de puncte care trebuie să fie obţinute în fiecare stagiu, să se determine numărul de posibilităţi modulo <code>578537</code> pentru ca jocul să se termine cu succes.

= Date de intrare =
Fișierul de intrare <code>sumkIN.txt</code> conține pe prima linie două numere naturale <code>N K</code> cu semnificația descrisă anterior.

= Date de ieșire =
Fișierul de ieșire <code>sumkOUT.txt</code> va conține pe prima linie un singur număr natural <code>P</code> reprezentând numărul total de posibilităţi modulo <code>578537</code> pentru ca jocul să se termine cu succes. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ K ≤ N ≤ 500</code>
* Fie <code>x</code> punctajul final într-un stagiu oarecare. Atunci dacă <code>x ≠  K</code>, jocul se termină cu eșec.
* Pentru <code>20%</code> din teste, <code>K ≤ N ≤ 10</code>, iar pentru <code>30%</code> din teste, <code>K≤N≤100</code>

= Exemplu 1: =
<code>sumkIN.txt</code>
 2 2
<code>sumkOUT.txt</code>
 5

= Exemplu 2: =
<code>sumkIN.txt</code>
 2 3
<code>sumkOUT.txt</code>
 Datele nu corespund restrictiilor impuse.

== Rezolvare == 
<syntaxhighlight lang="python" line="1">
def calcul(z1, z2, n, a):
    x = [0] * 502
    for j in range(1, n + 1):
        s = 0
        for i in range(1, j + 1):
            t = z1[i]
            t = (t * z2[j - i + 1]) % a
            s = (s + t) % a
        x[j] = s
    for j in range(1, n + 1):
        z1[j] = x[j]

def main():
    try:
        with open("sumkIN.txt", "rt") as fin:
            n, k = map(int, fin.readline().split())
    except Exception as e:
        with open("sumkOUT.txt", "wt") as fout:
            fout.write("Eroare la citirea datelor de intrare.")
        return

    if not (1 <= k <= n <= 500):
        with open("sumkOUT.txt", "wt") as fout:
            fout.write("Datele nu corespund restrictiilor impuse.")
        return

    r = [0] * 502
    z = [0] * 502
    r[1] = 1
    a = 578537

    for j in range(1, k + 1):
        for i in range(2, n + 1):
            r[i] = (r[i - 1] + r[i]) % a

    v = n
    z[1] = 1
    while v != 0:
        if v % 2 == 1:
            calcul(z, r, n, a)
        calcul(r, r, n, a)
        v = v // 2

    s = 0
    for i in range(1, n + 1):
        s = (s + z[i]) % a

    with open("sumkOUT.txt", "wt") as fout:
        fout.write(f"{int(s)}")

if __name__ == "__main__":
    main()

</syntaxhighlight>