Revizia anterioară Revizia următoare
| 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, sortate crescător după valoare. După o extragere de la bancomat mai primeşti un teanc cu M bacnote, sortate şi ele după valoare. Vrei să le adaugi în portofel astfel încât la final să fie toate sortate. 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 ordine dintre ele se păstrează. Care este numărul minim de mutări?
Date de intrare
Fişierul de intrare portofel.in conţine pe primia linie numărul de teste T. 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, M ≤ 5$
- 1 ≤ N, M ≤ 100000$
- 1 ≤ valorile bancnotelor ≤ 1000000000$
Exemplu
| portofel.in | portofel.out |
|---|---|
| 2 8 6 1 1 1 5 5 100 100 100 1 1 5 100 100 500 9 6 1 1 1 5 5 100 100 100 200 1 1 100 100 500 | 2 3 |
Explicaţie
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 al doilea caz este nevoie de 3 mutări, de exemplu: 1 [1 1] 1 1 5 5 [100 100] 100 100 100 200 [500].
