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 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 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 cd.out 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

cd.in

cd.out

Explicație

Se obţine faptul că în prima cutie sunt 6 CD-uri, în a doua 3 CD-uri, iar în a treia 3 CD-uri.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema CD:

#include <fstream>

using namespace std;

int main()
{
    int n,s,i,a[302],t,c,d;
    ifstream f("cd.in");
    f>>n>>s;

    s=s/n;

    for (i=1;i<=n;i++)
        a[i]=s;

    for (i=1;i<=n;i++) {
        f>>c>>d;
        a[i]=a[i]+c;
        a[d]=a[d]-c;
    }

    t=1;
    for (i=1;i<=n;i++)
        t=t*(a[i]-1) % 9901;

    f.close();

    ofstream g("cd.out");
    g<<t<<"
";
    g.close();
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #721 CD

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #721 CD de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #721 CD