Fișierul intrare/ieșire | sir2.in, sir2.out | Sursă | ad-hoc |
---|---|---|---|
Autor | Carmen Mincă | Adăugată de | Victor Manz • vmanz |
Timp de execuție pe test | 0.1 sec | Limită de memorie | 2048 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Sir2
Fie N și M două numere naturale nenule.
Fie X un șir de M numere naturale nenule X 1 , X 2 , … , X M cu proprietatea că N = X 1 + X 2 + ... + X M
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 ș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
- 2 ≤ M < N ≤ 300
- Două șiruri de numere naturale a 1, a 2, … , a M și b 1, b 2, … , b M sunt distincte dacă există cel puțin un indice k (kϵ{1, 2, … , M}) astfel încât a k ≠ b k .
- 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.
Exemple
sir2.in | sir2.out |
---|---|
4 3 |
2 3 |
6 3 |
4 10 |
Explicații
- Pentru primul exemplu: 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
- Pentru cel de-al doilea exemplu: cel mai mare număr care poate să apară în șirul X este 4.
Sunt 10 șiruri X distincte 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