Fişierul intrare/ieşire:portofel.in, portofel.outSursăRomanian Collegiate Programming Contest 2019
AutorPaul DiacAdăugată deRCPC2019RCPC2019 RCPC2019
Timp execuţie pe test0.4 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/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.inportofel.outExplicaţ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].
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?