== include(page="template/taskheader" task_id="portofel") ==
Poveste şi cerinţă...
Ai în portofel un teanc cu **N** bancnote, ordonate crescător după valoare. După o extragere de la bancomat mai primeşti un teanc cu **M** bancnote, ordonate şi ele după valoare. Vrei să le adaugi în portofel astfel încât la final să fie toate ordonate crescător. La o mutare poţi lua o secvenţă de bancnote consecutive dintre cele scoase din bancomat şi le poţi introduce la o anumita poziţie între cele din portofel, iar ordinea dintre ele se păstrează. Care este numărul minim de mutări pentru a adăuga toate bancnotele în portofel?
h2. Date de intrare
Fişierul de intrare $portofel.in$ ...
Fişierul de intrare $portofel.in$ conţine pe primia linie numărul de teste **T**. Apoi, pentru fiecare test în ordine, sunt scrise pe câte trei linii configuraţiile testelor. Pe prima linie sunt scrise numerele **N** şi **M**. Următoarea linie conţine valorile bancnotelor care sunt iniţial în portofel, iar pe următoarea linie sunt scrise valorile bancnotelor scoase din bancomat.
h2. Date de ieşire
În fişierul de ieşire $portofel.out$ ...
În fişierul de ieşire $portofel.out$ afişaţi **T** linii cu răspunsurile pentru fiecare test, în ordine.
h2. Restricţii
* $... ≤ ... ≤ ...$
* 1 ≤ **T** ≤ 5
* 1 ≤ **N**, **M** ≤ 10^5^
* 1 ≤ valorile bancnotelor ≤ 10^9^
h2. Exemplu
table(example). |_. portofel.in |_. portofel.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
table(example). |_. portofel.in |_. portofel.out |_. Explicaţie |
| 2
8 6
1 1 1 5 5 100 100 100
1 1 5 100 100 500
9 5
1 1 1 5 5 100 100 100 200
1 1 100 100 500
| 2
3
| Pentru primul caz se pot muta primele 3 bancnote iar la a doua mutare ultimele 3.
La final în portofel vor fi: 1, 1, 1, [1, 1, 5,] 5, 5, 100, 100, 100, [100, 100, 500],
unde între paranteze pătrate sunt bancnotele din bancomat.
Pentru testul doi e nevoie de 3 mutări, de exemplu: 1, [1, 1,] 1, 1, 5, 5, [100, 100,] 100, 100, 100, 200, [500].
|
== include(page="template/taskfooter" task_id="portofel") ==
