| Fişierul intrare/ieşire: | seriale.in, seriale.out | Sursă | Algoritmiada 2016 Runda 1 Seniori |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Seriale
Plictisit pana peste cap de facultate, Bossanip s-a apucat sa se uite la seriale. El are atat de multe de vazut incat nici nu mai stie in ce ordine sa le vizioneze. Dupa multe zile de cercetare a ajuns la urmatorul algoritm de vizionare a serialelor: Initial, acesta asociaza fiecarul serial un indice natural distinct. Cu cat indicele serialului este mai mare, cu atat serialul este mai bun. La urmatorul pas a impartit serialele in 2 liste: o lista cu N seriale si o lista cu K seriale (in total avem N + K seriale, fiecare avand un indice diferit din intervalul [1, N + K]). Deoarece nu vrea sa se uite la seriale de la cele mai bune la cele mai slabe sau invers (ca s-ar plictisi pe final, respectiv la inceput), el s-a hotarat sa selecteze din prima lista o data cel mai bun serial, dupa cel mai slab serial, dupa din nou cel mai bun si din nou cel mai slab etc. De fiecare data cand selecteaza un serial din prima lista, acesta selecteaza un serial din lista 2 (pe care vrea el) si il introduce in lista 1 (unde vrea el). Astfel, la fiecare moment de timp in lista 1 sunt N seriale.
Acum Bossanip va fi putin penal. El observa ca de fiecare data cand selecteaza cel mai mare/cel mai mic element, trebuie sa itereze prin toata lista de lungime N si sa stearga elementul de acolo (deoarece initial el are o lista cu serialele doar ca intr-o ordine aleatoare). Lenes de fire, el ar vrea ca cel mai mic element sa fie mereu in stanga si cel mai mare element in dreapta. Ca sa fie sigur ca totul e bine, ar prefera sa sorteze lista. Bossanip nu stie nici un algoritm de sortare, dar stie treapuri si poate foarte usor sa scoata un element din lista si sa introduca alt element unde vrea el.
Deoarece Bossanip nu are viziune asupra lumii, perspectiva narativa sau nici un fel de profunzime matematica, el va roaga pe voi sa aflati numarul minim de pasi(sau dupa cate seriale) o sa poata sa aibe lista sortata. Practic trebuie sa gasiti o strategie pentru alegerea serialelor din lista 2 si a pozitiilor unde vor fi inserate, astfel incat lista 1 sa devina sortata cat mai devreme.
Date de intrare
Fişierul de intrare seriale.in va contine pe prima linie 2 numere naturale N si K. Pe linia 2 vor fi N numere reprezentand indicii serialelor din prima grupa. Pe linia 3 vor fi K numere reprezentand indicii serialelor din grupa 2.
Date de ieşire
Fişierul de ieşire seriale.out va contine un singur numar natural reprezentand numarul minim de pasi necesari sa sortezi prima lista sau -1 daca nu se poate in K operatii. Dupa ce a vizionat K seriale si lista 2 devine goala, Bossanip se opreste. In caz ca lista 1 nu a devenit sortata, acesta considera ca nu si-a atins scopul (si desigur afiseaza -1).
Restricţii
- 1 ≤ N ≤ 100.000
- 1 ≤ K ≤ 200.000
- Valorile din cele doua liste sunt numere naturale distincte din intervalul [1, N + K]
- Pentru 10% din teste N, K ≤ 8
- Pentru 30% din teste N, K ≤ 100
- Pentru 60% din teste N, K ≤ 4000
Exemplu
| seriale.in | seriale.out |
|---|---|
| 5 5 3 1 5 2 4 6 8 7 9 10 | 4 |
Explicaţie
La primul pas Bossanip o sa se uite la cel mai bun serial din prima lista (cel cu indicele 5) si o sa introduca serialul 7 in capatul listei. Lista o sa arate: 3 1 2 4 7. La pasul 2 o sa se uite la 1 si intra 8 (lista va fi 3 2 4 7 8). La pasul 3, 9 o sa intre in locul lui 8. Dupa pasul 4 (ultimul pas), 2 o sa fie eliminat, intra 10 in capat si lista va fi 3 4 7 9 10 (care este sortata).
