| Fişierul intrare/ieşire: | portofel.in, portofel.out | Sursă | Romanian Collegiate Programming Contest 2019 |
| Autor | Paul Diac | Adăugată de |  RCPC2019 •RCPC2019 |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 16384 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Portofel
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?
Date de intrare
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.
Date de ieşire
În fişierul de ieşire portofel.out afişaţi T linii cu răspunsurile pentru fiecare test, în ordine.
Restricţii
- 1 ≤ T ≤ 5
- 1 ≤ N, M ≤ 105
- 1 ≤ valorile bancnotelor ≤ 109
Exemplu
| 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]. |
