Rezolvare PBinfo #956

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