Rezolvare completă PbInfo #956 sir2

Fie N și M două numere naturale nenule. Fie X un șir de M numere naturale nenule x1, x2,…, xM, cu proprietatea că
N=x1+x2+ ... +xM.

Cerinţă

Scrieţi un program care să citească numerele N și M şi care să determine:
a) cel mai mare număr care poate să apară în șirul X cu proprietatea din enunț;
b) numărul de șirurilor distincte X cu proprietatea din enunț, modulo 104729.

Date de intrare

Fișierul de intrare sir2.in conține pe prima linie cele două numere naturale N și M, separate printr-un singur spațiu.

Date de ieșire

Fișierul de ieșire sir2.out va conține

  • pe prima linie un număr natural reprezentând răspunsul la cerința a).
  • pe a doua linie un număr natural reprezentând răspunsul la cerința b).

Restricții și precizări

  • 2 ≤ M ≤ N ≤ 300
  • Două șiruri de numere naturale a1, a2, …, aM și b1, b2, …, bM sunt distincte dacă există cel puțin un indice k (kϵ{1,2,…,M}) astfel încât ak ≠ bk
  • Dacă y este un număr natural atunci y modulo 104729 reprezintă restul împărţirii lui y la 104729.
  • Pentru rezolvarea corectă a cerinței a) se acordă 20% din punctaj iar pentru rezolvarea corectă a cerinței b) se acordă 80% din punctaj.

Exemplu

sir2.in

4 3

sir2.out

2
3

Explicație

Cel mai mare număr care poate să apară în șirul X este 2. Sunt 3 șiruri X cu proprietatea din enunț și anume:

1, 1, 2
1, 2, 1
2, 1, 1

Exemplu

sir2.in

6 3

sir2.out

4
10

Explicație

Cel mai mare număr care poate să apară în șirul X este 4. Sunt 10 șiruri X cu proprietatea din enunț și anume:

1, 1, 4
1, 2, 3
1, 3, 2
1, 4, 1
2, 1, 3
2, 2, 2
2, 3, 1
3, 1, 2
3, 2, 1
4, 1, 1

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 sir2:

#include <iostream>
#include <fstream>

using namespace std;

ifstream f ("sir2.in");
ofstream g ("sir2.out");

const int mod = 104729;
int n, k;
int combinari[301];
//n pe orizontala
//k pe verticala

inline void maxim () {
    g<<n-k+1<<'\n';
}

inline void citeste () {
    f>>n>>k;
    maxim ();
    n--;
    k--;
    k = min (k, n-k);
}


inline void calculeaza () {
    combinari[0] = 1;
    for (int i=1; i<=n; i++) {
        for (int j=k; j>=1; j--) {
            combinari[j] = (combinari[j] + combinari[j-1]) % mod;
            //g<<combinari[j]<<' ';
        }
        //g<<endl;

    }
}


int main () {
    citeste ();
 // f>>n>>k;
    calculeaza ();
    g<<combinari[k]<<'\n';
    return 0;
}

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 #956 sir2

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #956 sir2 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!