Editing 2000 - Sir9

Corneluș a învățat să numere. El pornește întotdeauna de la <code>1</code>, numără din <code>1</code> în <code>1</code>, 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ă (<code>U</code>), câte numere spune în total (<code>N</code>) și, pentru a aprecia cât de ezitant este, numărul maxim de repetări (<code>R</code>) ale unei valori. De exemplu, el poate număra până la <code>8</code> astfel: <code>1 2 3 3 4 5 6 7 7 7 7 8 8</code>. În acest caz, numără până la <code>8</code> (<code>U=8</code>), spune <code>13</code> numere (<code>N=13</code>) și ezită cel mai mult la <code>7</code>, spunându‑l de <code>4</code> ori (<code>R=4</code>).

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

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

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

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

= Date de ieșire =
În fișierul <code>sir9.out</code> se scrie o singură valoare, astfel:

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

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

= Restricții și precizări =

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

= Exemplul 1 =
<code>sir9.in</code>
 1 5 3
<code>sir9.out</code>
 6

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

= Exemplul 2 =
<code>sir9.in</code>
 2 5 2
<code>sir9.out</code>
 8

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

= Exemplul 3 =
<code>sir9.in</code>
 2 10 3
<code>sir9.out</code>
 274

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

== Rezolvare ==
<syntaxhighlight lang="python3">
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()

</syntaxhighlight>