h3. Soluţie:

Soluţia problemei se poate deduce urmând paşii următori. Să presupunem că avem cărţile $A B C$ iniţial şi $K = 3$. Dacă îl vom adăuga pe $D$, atunci nu vor rămâne importante decât cărţile $D A B$, deoarece, dacă vom roti ulterior ultimele $K$ cărţi, $C$ nu va mai fi niciodată considerat, cărţile fiind doar adăugate, iar o dată ce o carte iese din „top {$K$}” cărţi nu va mai fi posibil să i se schimbe poziţia pe raft. Să rotim acum „top {$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, în această ordine, $D C$. Proprietatea celor $K$ cărţi din vârf este: 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$.
 
Întrucât operaţiile unui deque se execută în $O(1)$ amortizat, soluţia are complexitatea $O(N + M)$.

Va urma...

h3. 'Sir':problema/sir