2000 - Sir9

Corneluș a învățat să numere. El pornește întotdeauna de la 1, numără din 1 în 1, nu greșește niciodată numărul următor, însă ezită uneori și atunci spune numărul curent de mai multe ori. Sora lui, Corina, îl urmărește și face tot felul de calcule asupra modurilor în care numără fratele ei. Astfel, ea urmărește până la cât numără (U), câte numere spune în total (N) și, pentru a aprecia cât de ezitant este, numărul maxim de repetări (R) ale unei valori. De exemplu, el poate număra până la 8 astfel: 1 2 3 3 4 5 6 7 7 7 7 8 8. În acest caz, numără până la 8 (U=8), spune 13 numere (N=13) și ezită cel mai mult la 7, spunându‑l de 4 ori (R=4).

Cerințe

1) Cunoscând numărul total de numere N și ultimul număr spus U, trebuie să calculați câte șiruri diferite au exact N numere și se termină cu numărul U.

2) Cunoscând numărul total de numere N și numărul maxim de repetări R ale unei valori, trebuie să calculați câte șiruri diferite au exact N numere și fiecare valoare se repetă de cel mult R ori.

Deoarece numărul de șiruri poate fi foarte mare, calculați restul împărțirii acestui număr la 20173333.

Date de intrare

Din fișierul sir9.in se citesc trei numere naturale, P, N și X, scrise în această ordine, cu câte un spațiu între ele. P poate avea una dintre valorile 1 sau 2, iar N este numărul de numere din șir. Când P are valoarea 1, numărul X reprezintă ultimul număr spus (U), iar când P are valoarea 2, X reprezintă numărul maxim de repetări ale unei valori (R).

Date de ieșire

În fișierul sir9.out se scrie o singură valoare, astfel:

• dacă P a avut valoarea 1, valoarea reprezintă numărul de șiruri distincte care au exact N numere și se termină cu numărul X;
• dacă P a avut valoarea 2, valoarea reprezintă numărul de șiruri distincte care au exact N numere și fiecare număr se repetă de cel mult X ori.

În ambele cazuri, deoarece numărul rezultat poate fi foarte mare, se va scrie restul împărțirii acestui număr la 20173333.

Restricții și precizări

• 1 ≤ N ≤ 100.000
• X ≤ N
• testele cu P=1 vor totaliza 50% din punctaj, restul de 50% din punctaj fiind pentru P=2;
• pentru teste cumulând 50 de puncte valoarea lui N nu depășește 1000;
• Ultima valoare spusă poate să apară de mai multe ori.

Exemplul 1

sir9.in

1 5 3

sir9.out

6

Explicație

Se rezolvă cerința 1. Pentru N=5, X=3, sunt 6 șiruri care au exact N numere și se termină cu 3: 1 1 1 2 3, 1 1 2 2 3, 1 1 2 3 3, 1 2 2 2 3, 1 2 2 3 3, 1 2 3 3 3.

Exemplul 2

sir9.in

2 5 2

sir9.out

8

Explicație

Se rezolvă cerința 2. Pentru N=5, X=2, sunt 8 șiruri care au exact N numere și fiecare număr se repetă de cel mult 2 ori: 1 1 2 2 3, 1 1 2 3 3, 1 1 2 3 4, 1 2 2 3 3, 1 2 2 3 4, 1 2 3 3 4, 1 2 3 4 4, 1 2 3 4 5.

Exemplul 3

sir9.in

2 10 3

sir9.out

274

Explicație

Se rezolvă cerința 2. Pentru N=10, X=3, sunt 274 de șiruri care au exact 10 numere și fiecare număr se repetă de cel mult 3 ori.

Rezolvare

MOD = 20173333  

def count_sequences_ending_with_u(n, u):
    dp = [[0 for _ in range(u + 1)] for _ in range(n + 1)]

    for i in range(u + 1):
        dp[0][i] = 1 

    for i in range(1, n + 1):
        for j in range(u + 1):
            dp[i][j] = 0

            for k in range(1, j):
                if j >= k:
                    dp[i][j] += dp[i - 1][j - k]
                    if j >= 2:
                        dp[i][j] += dp[i - 1][j - 2]

    return dp[n][u] % MOD

def count_sequences_with_max_repeats_r(n, r):
    dp = [[0 for _ in range(r + 1)] for _ in range(n + 1)]

    for i in range(r + 1):
        dp[0][i] = 1  

    for i in range(1, n + 1):
        for j in range(r + 1):
            dp[i][j] = 0

            for k in range(1, j):
                if j >= k:
                    dp[i][j] += dp[i - 1][j]
                    if j >= 2:
                        dp[i][j] += dp[i - 1][j - 1]

    return dp[n][r] % MOD

def main():
    with open("sir9.in", "r") as input_file:
        p, n, x = map(int, input_file.readline().split())

    if p == 1:
        sequences_count = count_sequences_ending_with_u(n, x)
    else:
        sequences_count = count_sequences_with_max_repeats_r(n, x)

    with open("sir9.out", "w") as output_file:
        output_file.write(str(sequences_count))

if __name__ == "__main__":
    main()