march

March

* I(k,c) = inserează cifra c pe poziţia k;
* D(k) = şterge cifra de pe poziţia k;
* C(k,c) = înlocuieşte cifra de pe locul k cu cifra c.

Pentru obţinerea primului număr se fac doar operaţii de inserare.
Tommy trebuie să gestioneze şi comenzile pe care le primeşte. Pentru fiecare comandă, Tommy ştie numărul de mărţişoare comandate. El trebuie să trimită solicitantului cutii cu mărţişoare, aflate pe poziţii consecutive pe bandă, astfel încât numărul de mărţişoare timise să fie cel puţin egal cu numărul mărţişoarelor comandate.
h2. Date de intrare

Fişierul de intrare $march.in$ ...

Fişierul de intrare *march.in* conţine pe prima linie un număr natural v reprezentând cerinţa care trebuie să fie rezolvată (1,2 sau 3). Pe cea de a doua linie se află numerele naturale n şi m, cu semnificaţia din enunţ.
Pe următoarea linie se află n numere naturale, separate prin spaţiu, reprezentând numerele scrise pe cutii, în ordinea în care sunt aşezate pe bandă.

h2. Date de ieşire

În fişierul de ieşire $march.out$ ...

Dacă cerinţa este *v=1*, atunci pe prima linie a fişierului *march.out* va fi scris un număr natural reprezentând numărul minim de operaţii pe care Tommy trebuie să le facă pentru a eticheta toate cele n cutii.
Dacă cerinţa este *v=2*, atunci fişierul de ieşire *march.out* va conţine, pe prima linie, un număr natural reprezentând numărul de posibilităţi distincte în care Tommy poate onora comanda.
Dacă cerinţa este *v=3*, atunci fişierul de ieşire *march.out* va conţine, pe prima linie, un număr natural reprezentând numărul minim de cutii ce pot fi trimise, astfel încât comanda să poată fi onorată.

h2. Restricţii

* $... ≤ ... ≤ ...$

* 2 ≤ n ≤ 1000
* 1 &le; m &le; <tex>2^{64} - 1$</tex>
* eticheta oricărei cutii este un număr natural din intervalul <tex>$[ 1; 2^{64} - 1 ]$</tex>;
* două posibilităţi de onorare a comenzii sunt distincte dacă şirul format de numerele de ordine al cutiilor diferă;
* m &le; numărul de mărţişoare aflate în cele n cutii;
* Pentru 50% dintre teste cerinţa este 1, pentru 30% dintre teste cerinţa este 2 şi pentru 20% dintre teste cerinţa este 3.
 

h2. Exemplu
table(example). |_. march.in |_. march.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 1
5 3500
1234 3134 313 143 123
| 10

|

| 2
5 3500
1234 3134 313 143 123
| 6
|
| 3
5 3500
1234 3134 313 143 123
| 2
|

h3. Explicaţie

...

h3. Pentru primul exemplu:
 
Pentru a scrie cele cele 5 numere se folosesc minimum 10 operaţii:
<tex>
\overset{I(1,1)}{\longrightarrow} 1 \overset{I(2,2)}{\longrightarrow} 12 \overset{I(3,3)}{\longrightarrow} 123 \overset{I(4,4)}{\longrightarrow} \textcolor{red}{1234} \overset{d(2)}{\longrightarrow} 134 \overset{I(1,3)}{\longrightarrow} \textcolor{red}{3134} \overset{D(4)}{\longrightarrow} \textcolor{red}{313} \overset{D(1)}{\longrightarrow} 13 \overset{I(2,4)}{\longrightarrow} \textcolor{red}{143} \overset{C(2,2)}{\longrightarrow} \textcolor{red}{123}
</tex>
&nbsp;
 
h3. Pentru al doilea exemplu:
 
Sunt 6 modalităţi de onorare a comenzii celor 3500 de mărţişoare:
 
* 1234+3134
* 1234+3134+313
* 1234+3134+313+143
* 1234+3134+313+143+123
* 3134+313+143
* 3134+313+143+123
&nbsp;
 
h3. Pentru al treilea exemplu:
 
Pentru onorarea comenzii, trebuiesc trimise cel puţin 2 cutii (1234+3134)

== include(page="template/taskfooter" task_id="march") ==