h3. Soluţie:
Soluţia problemei se poate deduce pe baza observaţiei următoare: odată avansată dincolo de poziţia $K$, o carte ajunge pe poziţia finală, întrucât orice operaţie ulterioară (inserare sau rotaţie) nu o va mai afecta. Să presupunem că iniţial avem cărţile $A B C$ şi $K = 3$. Dacă îl vom adăuga pe $D$, atunci nu avem nevoie pentru operaţiile următoare decât de cărţile $D A B$, deoarece, dacă vom roti ulterior ultimele $K$ cărţi, $C$ nu va mai fi niciodată considerat. Să rotim acum primele $K$ cărţi. Noua ordine va fi $B A D$ şi $C$ pe raft la loc sigur. Dacă îl vom adăuga pe $E$, topul se va schimba în $E B A$, iar pe raft, în mod sigur vor fi $D C$, în această ordine. Cele $K$ cărţi din vârf se prezintă ca o secvenţă continuă de elemente, la care se adaugă noi elemente sau se elimină dintre acestea numai pe la _capete_. Aceste capete sunt chiar $head$ şi $tail$ ale unui deque.
Soluţia problemei se poate deduce pe baza observaţiei următoare: odată avansată dincolo de poziţia $K$, o carte ajunge pe poziţia finală, întrucât orice operaţie ulterioară (inserare sau rotaţie) nu o va mai afecta. Să presupunem că iniţial avem cărţile $A B C$ şi $K = 3$. Dacă îl vom adăuga pe $D$, atunci nu avem nevoie pentru operaţiile următoare decât de cărţile $D A B$, deoarece, dacă vom roti ulterior primele $K$ cărţi, $C$ nu va mai fi niciodată considerat. După o rotaţie, noua ordine va fi $B A D$ şi $C$ va fi pe raft la loc sigur. Dacă îl vom adăuga pe $E$, topul se va schimba în $E B A$, iar pe raft, în mod sigur vor fi $D C$, în această ordine. Cele $K$ cărţi din vârf se prezintă ca o secvenţă continuă de elemente, la care se adaugă noi elemente sau se elimină dintre acestea numai pe la _capete_. Aceste capete sunt chiar $head$ şi $tail$ ale unui $deque$.
p=. !deque-si-aplicatii?bookpile.png 40%!
La final, când se vor termina operaţiile, cărţilor de pe raft li se vor adăuga cele din deque şi se va afişa soluţia. În cazul presupus, soluţia va fi: $E B A D C$.
La final, când se vor termina operaţiile, cărţilor de pe raft li se vor adăuga cele din $deque$ şi se va afişa soluţia. În cazul presupus, soluţia va fi: $E B A D C$.
Întrucât operaţiile unui deque se execută în timp $O(1)$, soluţia are complexitatea $O(N + M)$.
