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

<syntaxhighlight lang="python" line>

1. 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>