Fişierul intrare/ieşire:	march.in, march.out	Sursă	ProSoft@NT 2017
Autor	Cristina Sichim	Adăugată de	Valentin Rosca •valiro21
Timp execuţie pe test	0.1 sec	Limită de memorie	5120 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

March

În România, luna martie este luna în care sărbătorim primăvara. Conform tradiţiei, de 1 martie, oferim mărţişoare celor dragi. Fabrica ,,Spring Time” produce mărţişoare. Acestea sunt ambalate în cutii şi aşezate, în ordine, pe o bandă. Pe fiecare cutie este lipită o etichetă cu numărul mărţişoarelor din cutie.
Tommy este managerul acestui magazin şi lui îi revine sarcina de a eticheta cutiile cu mărţişoare. Pentru a fi cât mai operativ, Tommy realizează etichetele pe calculator, şi, de fiecare dată obţine numărul care trebuie scris pe cutie din numărul scris anterior (cu excepţia primului număr), făcând cât mai puţine operaţii de tipul:

• 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.

Date de intrare

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ă.

Date de ieşire

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ă.

Restricţii
[Unparseable or potentially dangerous LaTeX formula! Error 5 : 813x22];

• două posibilitati de onorare a comenzii sunt distincte daca sirul format de numerele de ordine al cutiilor difera;

• 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.

Exemplu

Explicaţie

...

Cum se trimit solutii?