Fişierul intrare/ieşire:sir2.in, sir2.outSursăad-hoc
AutorCarmen MincaAdăugată devmanzVictor Manz vmanz
Timp execuţie pe test0.1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.insir2.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici