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 ⩽ n ⩽ 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

Exemplu 2

cdin.txt

0 -1

cdout.txt

Nu au fost respectate cerintele impuse

Rezolvare

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