Fişierul intrare/ieşire:calcule.in, calcule.outSursăOJI 2013 Clasa a 10-a
AutorGheorghe ManolacheAdăugată decocoClaudiu coco
Timp execuţie pe test0.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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

calcule.incalcule.out
10 3
5 3 8 6 9 6 2 7 9 6
4
23

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici