Revizia anterioară Revizia următoare
| 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 indroduce in lista 1. Astfel, la fiecare moment de timp in lista 1 sunt N seriale.
Acum Bossanip o sa fie 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 el are o lista initial 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 muschiul lui.
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 terbuie sa gasiti o strategie optima de a alege ce serial introduceti din lista 2 si unde)
Date de intrare
Fişierul de intrare seriale.in ...
Date de ieşire
În fişierul de ieşire seriale.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| seriale.in | seriale.out |
|---|---|
| 5 5 3 1 5 2 4 7 9 8 10 11 | 4 |
Explicaţie
...
