Fișierul intrare/ieșire sir2.in, sir2.out Sursă ad-hoc
Autor Carmen Mincă Adăugată de avatar vmanz Victor Manz vmanz
Timp de execuție pe test 0.1 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii