march

March

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") ==