Fişierul intrare/ieşire:sirul2.in, sirul2.outSursăOJI 2017, clasa a 10-a
AutorRodica PinteaAdăugată debciobanuBogdan Ciobanu bciobanu
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sirul2

Corneluş a învăţat să numere. El porneşte întotdeauna de la 1, numără din 1 în 1, nu greşeşte niciodată numărul următor, însă ezită uneori şi atunci spune numărul curent de mai multe ori. Sora lui, Corina, îl urmăreşte şi face tot felul de calcule asupra modurilor în care numără fratele ei. Astfel, ea urmăreşte până la cât numără U, câte numere spune în total N şi, pentru a aprecia cât de ezitant este, numărul maxim de repetări R ale unei valori. De exemplu, el poate număra până la 8 astfel: 1, 2, 3, 3, 4, 5, 6, 7, 7, 7, 7, 8, 8. În acest caz, numără până la 8 (U=8), spune 13 numere (N=13) şi ezită cel mai mult la 7, spunându‑l de 4 ori (R=4).

Cerinţe

  1. Cunoscând numărul total de numere N şi ultimul număr spus U, trebuie să calculaţi câte şiruri diferite au exact N numere şi se termină cu numărul U.
  2. Cunoscând numărul total de numere N şi numărul maxim de repetări R ale unei valori, trebuie să calculaţi câte şiruri diferite au exact N numere şi fiecare valoare se repetă de cel mult R ori.

Date de intrare

Din fişierul sirul2.in se citesc trei numere naturale, P, N şi X, scrise în această ordine, cu câte un spaţiu între ele. P poate avea una dintre valorile 1 sau 2, iar N este numărul de numere din şir. Când P are valoarea 1, numărul X reprezintă ultimul număr spus U, iar când P are valoarea 2, X reprezintă numărul maxim de repetări ale unei valori R.

Date de ieşire

În fişierul sirul2.out se scrie o singură valoare, astfel:

  • Dacă P a avut valoarea 1, valoarea reprezintă numărul de şiruri distincte care au exact N numere şi se termină cu numărul X;
  • Dacă P a avut valoare 2, valoarea reprezintă numărul de şiruri distincte care au exact N numere şi fiecare număr se repetă de cel mult X ori.

În ambele cazuri, deoarece numărul rezultat poate fi foarte mare, se va scrie restul împărţirii acestui număr la 20173333.

Restricţii

  • 1 ≤ N ≤ 100000
  • X ≤ N
  • Testele cu P=1 vor totaliza 50% din punctaj, restul de 50% din punctaj fiind pentru P=2.
  • Pentru teste cumulând 50 de puncte valoarea lui N nu depăşeşte 1000.
  • Ultima valoare spusă poate să apară de mai multe ori.

Exemplu

sirul2.insirul2.outExplicaţie
1 5 3
6
Se rezolvă cerinţa 1.
Pentru N=5, X=3, sunt 6 şiruri care au exact N numere şi se termină cu 3:
1 1 1 2 3
1 1 2 2 3
1 1 2 3 3
1 2 2 2 3
1 2 2 3 3
1 2 3 3 3
2 5 2
8
Se rezolvă cerinţa 2.
Pentru N=5, X=2, sunt 8 şiruri care au exact N numere şi fiecare număr se repetă de cel mult 2 ori:
1 1 2 2 3
1 1 2 3 3
1 1 2 3 4
1 2 2 3 3
1 2 2 3 4
1 2 3 3 4
1 2 3 4 4
1 2 3 4 5
2 10 3
274
Se rezolvă cerinţa 2.
Pentru N=10, X=3, sunt 274 de şiruri care au exact 10 numere şi fiecare număr se repetă de cel mult 3 ori.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?