Fişierul intrare/ieşire: | sir2.in, sir2.out | Sursă | ad-hoc |
Autor | Carmen Minca | Adăugată de | |
Timp execuţie pe test | 0.1 sec | Limită de memorie | 2048 kbytes |
Scorul tău | N/A | Dificultate |
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