problema/calcule

Calcule

== include(page="template/taskheader" task_id="calcule") ==
 
Gigel a studiat recent sirurile cu $n$ elemente, numere naturale. Pentru un astfel de sir $S$, Gigel doreste sa afle raspunsul la intrebarile:
 
# Care este numarul minim de subsiruri strict crescatoare in care se poate partitiona $S$?
# Care este numarul de secvente, modulo $20011$, cu suma elementelor divizibila cu $k$ care se pot obtine din $S$?
 
h2. 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.
 
h2. 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.
 
h2. 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)$.
 
h2. 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!
 
h2. Exemplu
 
table(example). |_. calcule.in |_. calcule.out |
| 10 3
5 3 8 6 9 6 2 7 9 6
| 4
  23
|
 
h3. Explicaţie
 
# O partitie cu numar minim ( $4$ ) de subsiruri crescatoare este urmatoarea:
$5 6 7 9$
$3 6 9$
$8$
$2 6$
# Exista $23$ de secvente cu suma divizibila cu $3$. Iata doua dintre acestea:
$3$
$6 2 7$
 
== include(page="template/taskfooter" task_id="calcule") ==

public

task: calcule

9943