Editing 0721 - CD

== Enunt ==
Ionică a strâns foarte multe CD-uri cu jocuri, muzică, filme, etc. pe care le are aşezate în n cutii, codificate prin 1, 2, …, n. Pe la Ionică vine în vizită vărul lui, Florin, care tocmai câştigase un concurs de matematică. Ca să-i mai taie din elan, Ionică îi propune lui Florin să pună o parte din CD-uri într-o ladă mai mare, astfel încât să se ia din fiecare cutie cel puţin câte un CD şi la sfârşit să rămână în fiecare cutie cel puţin un CD.

Pentru a complica problema, Ionică nu îi spune lui Florin câte CD-uri sunt în fiecare cutie, ci îi spune că are în total S CD-uri şi că, dacă ia din fiecare cutie un număr de CD-uri şi le pune în altă cutie va obţine în final acelaşi număr de CD-uri în toate cutiile.
== Cerința ==
Să se scrie un program care cunoscând n, S şi numărul de CD-uri mutate din fiecare cutie, determină numărul k de modalităţi distincte de introducere a CD-urilor în ladă, respectând regula din enunţ.
== Date de intrare ==
Fișierul de intrare cdin.txt conține pe prima linie numerele naturale n şi S separate printr-un spaţiu, iar pe următoarele n linii perechile de numere naturale y[i] c[i] separate printr-un spaţiu, corespunzătoare numărului de CD-uri y[i] , care se pun din cutia i în cutia c[i] , i=1,2,...,n.
== Date de ieșire ==
Fișierul de ieșire cdout.txt va conține pe prima linie numărul k modulo 9901.
== Restricții și precizări ==
*2 &les; n &les; 300
*În fiecare cutie sunt cel mult 1000 CD-uri.
*k modulo p reprezintă restul împărţirii lui k la p
*S modulo n = 0
*O modalitate de alegere a CD-urilor ce vor fi puse în ladă diferă de o altă modalitate, dacă din cel puţin o cutie se alege un număr diferit de CD-uri.
== Exemplu 1 ==
;cdin.txt
:3 12
:3 2
:2 3
:1 1
;cd.out
:20
<br>
== Exemplu 2 ==
;cdin.txt
:0 -1
;cdout.txt
: Nu au fost respectate cerintele impuse
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#0721 - CD
def read_input(file_name):
    try:
        with open(file_name, 'r') as file:
            n, S = map(int, file.readline().split())
            data = [tuple(map(int, line.split())) for line in file.readlines()]

            if not (2 <= n <= 300 and S % n == 0 and all(0 <= y <= 1000 and 1 <= c <= n for y, c in data)):
                raise ValueError("Numerele nu respecta restricțiile.")

            return n, S, data
    except Exception as e:
        print(f"Nu au fost respectate cerintele impuse: {str(e)}")
        return None


def write_output(file_name, result):
    with open(file_name, 'w') as file:
        if result is not None:
            file.write(f"{result}\n")


def count_ways(n, S, data):
    mod = 9901
    dp = [0] * (S + 1)
    dp[0] = 1

    for y, c in data:
        for i in range(S, y - 1, -1):
            dp[i] = (dp[i] + dp[i - y] - dp[i - y - 1] + mod) % mod

    return dp[S]


def main(input_file, output_file):
    result = read_input(input_file)
    if result is not None:
        n, S, data = result
        result = count_ways(n, S, data)
        write_output(output_file, result)


if __name__ == "__main__":
    main("cdin.txt", "cdout.txt")

</syntaxhighlight>