Ramona Dragoș: Pagină nouă: == 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 ce...

2023-12-31T13:41:54Z

Pagină nouă: == 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 ce...

New page

== 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>

0721 - CD - Revision history