# PBinfo #956 – sir2 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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

## Cod sursă C++

```cpp
#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;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/956)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/956/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-956/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)