Fişierul intrare/ieşire:cd.in, cd.outSursăLot Juniori 2010 - Baraj 1
AutorDoru Popescu AnastasiuAdăugată deGheorgheMihaiMihai Gheorghe GheorgheMihai
Timp execuţie pe test0.1 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cd

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ţă

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 cd.in 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 yi ci separate printr-un spaţiu, corespunzătoare numărului de CD-uri yi, care se pun din cutia i în cutia ci, i = 1, 2, ..., N.

Date de ieşire

În fişierul de ieşire cd.out se va afişa pe prima linie numărul K modulo 9901.

Restricţii

  • 2 ≤ N ≤ 300
  • În fiecare cutie sunt cel mult 1000 CD-uri.
  • 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

cd.incd.out
3 12
3 2
2 3
1 1
20
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content