Fișierul intrare/ieșire	calcule.in, calcule.out	Sursă	OJI 2013 Clasa a 10-a
Autor	Gheorghe Manolache	Adăugată de	Claudiu • coco
Timp de execuție pe test	0.05 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	2

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Calcule ( clasa a 10-a )

Gigel a studiat recent șirurile cu n elemente, numere naturale. Pentru un astfel de șir S, Gigel dorește să afle răspunsul la întrebările:

a) Care este numărul minim de subșiruri strict crescătoare în care se poate partiționa S?
b) Care este numărul de secvențe, modulo 20011, cu suma elementelor divizibilă cu k care se pot obține din S?

Cerinta

Dându-se un șir S cu n elemente numere naturale și un număr natural k se cere să se răspundă la cele două întrebări.

Date de intrare

Pe prima linie a fișierului calcule.in se află valorile naturale n și k separate printr-un spațiu. Pe următoarea linie se află cele n elemente ale șirului S, numere naturale separate prin câte un spațiu.

Date de ieșire

Fișierul calcule.out va conține două linii, pe prima linie fiind scris un număr natural reprezentând răspunsul la întrebarea a), iar pe a doua, un număr natural reprezentând răspunsul la întrebarea b).

Restricții

• 1 < n < 100 000
• S are elemente mai mici sau egale cu 20 000
• k < 50 000, k < n
• Un subșir al șirului S se obține selectând elemente din S în ordinea în care sunt în S, dar nu obligatoriu de pe poziții consecutive, iar o secvență a șirului S se obține selectând elemente în ordinea în care sunt în S, dar obligatoriu de pe poziții consecutive. Se admit și secvențe sau subșiruri cu un singur element.
• Pentru 50 % din teste k < 10 000
• Mai multe subșiruri ale lui S formează o partiție dacă elementele reuniunii subșirurilor pot fi reașezate astfel încât să se obțină exact S.
• x modulo y reprezintă restul împărțirii lui x la y.
• În situația în care nu ați reușit să rezolvați cerința a), dar aveți un răspuns pentru b), veți scrie răspunsul pentru cerința b) pe linia 2 și nu pe prima linie!

Exemplu

Explicație

a) O partiție cu număr minim (4) de subșiruri crescătoare este următoarea:
5 6 7 9
3 6 9
8
2 6
b)Există 23 de secvențe cu suma divizibilă cu 3. Iată două dintre acestea:
3
6 2 7