Fişierul intrare/ieşire:	sir2.in, sir2.out	Sursă	ad-hoc
Autor	Carmen Minca	Adăugată de	Victor Manz •vmanz
Timp execuţie pe test	0.1 sec	Limită de memorie	2048 kbytes
Scorul tău	N/A	Dificultate	2/5

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise

Sir2

Fie N şi M două numere naturale nenule.
Fie X un şir de M numere naturale nenule X ₁ , X ₂ , … , X _M cu proprietatea că N = X ₁ + X ₂ + ... + 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 ₁, a ₂, … , a _M şi b ₁, b ₂, … , 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

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