h2(#problema-1). 1. 'Book Pile':http://acm.sgu.ru/problem.php?contest=0&problem=271 (SGU)

bq. Se dau $N$ cărţi aşezate una deasupra celeilalte asupra cărora se vor efecta $M$ operaţii de două tipuri: 1. $ADD${$(nume)$} : se adaugă cartea $nume$ deasupra celorlalte; 2. $ROTATE$ : primele $K$ cărţi de deasupra se rotesc (dacă sunt mai puţin de $K$ cărţi atunci se vor roti toate; prin rotaţie vom considera elementele în ordine inversă: ultimul va fi primul, penultimul va fi al doilea etc). Se cere să se afişeze cărţile în ordine, prima fiind cea de deasupra, după efectuarea celor $M$ operaţii.

bq. Se dau $N$ cărţi aşezate una deasupra celeilalte asupra cărora se vor efectua $M$ operaţii de două tipuri: 1. $ADD${$(nume)$}: se adaugă cartea $nume$ deasupra celorlalte; 2. $ROTATE$: primele $K$ cărţi de deasupra se rotesc (dacă sunt mai puţin de $K$ cărţi atunci se vor roti toate). Rotaţia presupune inversarea celor $K$ elemente, adică ultimul va fi primul, penultimul va fi al doilea etc. Se cere să se afişeze cărţile în ordine, prima fiind cea de deasupra, după efectuarea celor $M$ operaţii.

Restricţii: $0 ≤ N, K ≤ 40 000$, $0 ≤ M ≤ 100 000$.
h3. Soluţie:

Soluţia problemei se poate deduce urmând paşii următori. Să presupunem că iniţial avem cărţile $A B C$ ş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.

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.

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)$.

Întrucât operaţiile unui deque se execută în timp $O(1)$, soluţia are complexitatea $O(N + M)$.

h2(#problema-2). 2. 'Vila 2':problema/vila2 (.campion, 2005)