Fişierul intrare/ieşire:calcule.in, calcule.outSursăOJI 2013, clasa a 10-a
AutorGheorghe ManolacheAdăugată devisanrVisan Radu visanr
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Calcule

Gigel a studiat recent sirurile cu n elemente, numere naturale. Pentru un astfel de sir S, Gigel doreste sa afle raspunsul la intrebarile:

  1. Care este numarul minim de subsiruri strict crescatoare in care se poate partitiona S?
  2. Care este numarul de secvente, modulo 20011, cu suma elementelor divizibila cu k care se pot obtine din S?

Cerinta

Dandu-se un sir S cu n elemente numere naturale si un numar natural k se cere sa se raspunda la cele doua intrebari.

Date de intrare

Pe prima linie a fisierului calcule.in se afla valorile naturale n si k separate printr-un spatiu. Pe urmatoarea linie se afla cele n elemente ale sirului S, numere naturale separate prin cate un spatiu.

Date de ieşire

Fisierul calcule.out va contine doua linii, pe prima linie fiind scris un numar natural reprezentand raspunsul la intrebarea 1), iar pe a doua, un numar natural reprezentand raspunsul la intrebarea 2).

Restricţii

  • 1 < n < 100 000
  • S are elemente mai mici sau egale cu 20 000
  • k < 50 000, k < n
  • Un subsir al sirului S se obtine selectand elemente din S in ordinea in care sunt in S, dar nu obligatoriu de pe pozitii consecutive, iar o secventa a sirului S se obtine selectand elemente in ordinea in care sunt in S, dar obligatoriu de pe pozitii consecutive. Se admit si secvente sau subsiruri cu un singur element.
  • Pentru 50% din teste k < 10 000
  • Pentru raspuns corect la o singura cerinta se acorda 50% din punctaj.
  • Mai multe subsiruri ale lui S formeaza o partitie daca elementele reuniunii subsirurilor pot fi reasezate astfel incat sa se obtina exact S.
  • x modulo y reprezinta restul impartirii lui x la y.
  • In situatia in care nu ati reusit sa rezolvati cerinta 1), dar aveti un raspuns pentru 2), veti scrie raspunsul pentru cerinta 2) pe linia 2 si nu pe prima linie!

Exemplu

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

Explicaţie

  1. O partitie cu numar minim ( 4 ) de subsiruri crescatoare este urmatoarea:
    5 6 7 9
    3 6 9
    8
    2 6
  2. Exista 23 de secvente cu suma divizibila cu 3. Iata doua dintre acestea:
    3
    6 2 7
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content