* '_Introducere_':deque-si-aplicatii#introducere
* '_Aplicaţii:_':deque-si-aplicatii#problema-1
** '1. Book Pile (SGU)':deque-si-aplicatii#problema-1

** '2. Vila 2 (.campion)':deque-si-aplicatii#problema-2

** '2. Vila 2 (.campion, 2005)':deque-si-aplicatii#problema-2

** '3. Şir':deque-si-aplicatii#problema-3

** '4. Trans (ONI 2004)':deque-si-aplicatii#problema-4
** '5. Otilia (.campion)':deque-si-aplicatii#problema-5
** '6. Bcrc (Stelele Informaticii)':deque-si-aplicatii#problema-6
** '7. Cut the Sequence (PKU)':deque-si-aplicatii#problema-7

** '4. Platforma (.campion, 2009)':deque-si-aplicatii#problema-4
** '5. Trans (ONI 2004)':deque-si-aplicatii#problema-5
** '6. Otilia (.campion, 2005)':deque-si-aplicatii#problema-6
** '7. Bcrc (Stelele Informaticii, 2006)':deque-si-aplicatii#problema-7
** '8. Cut the Sequence (PKU)':deque-si-aplicatii#problema-8

* '_Concluzii_':deque-si-aplicatii#concluzii
* '_Probleme suplimentare_':deque-si-aplicatii#probleme-suplimentare
* '_Bibliografie_':deque-si-aplicatii#bibliografie

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

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

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

bq. Se dă un şir $S$ de $N$ numere întregi şi un $D$ număr natural. Se cere să determine diferenţa maximă dintre oricare două numere din şir cu proprietatea că diferenţa indicilor nu depăşeşte $D$.
Restricţii: $2 ≤ N ≤ 100 000$, $1 ≤ D ≤ N/2$.

bq. Se dă un şir $S$ de numere întregi de lungime $N$. Se cere să se găsească secvenţa de lungime maximă cuprinsă între $X$ şi $Y$ astfel încât $MAX - MIN ≤ Z$, unde $MAX$ este maximul dintre toate numerele întregi din secvenţă iar $MIN$ minimul dintre acestea. Secvenţa soluţie va fi cea cu poziţia de început maximă dintre toate secvenţele de lungime maximă.
Restricţii: $3 ≤ N ≤ 100 000$, $1 ≤ X ≤ Y ≤ N$, $0 ≤ Z ≤ 30 000$.

h3. Soluţie

h3. Soluţie:

Voi prezenta mai jos o rafinare a soluţiei în trei paşi.

Complexitatea finală va fi $O(N)$.

h2(#problema-4). '4. Trans':problema/trans (ONI 2004)

h2(#problema-4). '4. Platforma':http://campion.edu.ro/problems/3/509/platforma_ro.htm (.campion, 2009)
 
bq. Se dă o matrice $P$ de dimensiuni $M x N$ cu elemente numere întregi. Se defineşte valoarea maximă dintr-un dreptunghi de dimensiuni $R x C$ ca fiind valoarea maximă dintre elementele aflate în acel dreptunghi.
Cerinţă: Să se găsească un dreptunghi de dimensiuni $R x C$ cu valoarea maximă minimă.
Restricţii: $1 ≤ M, N ≤ 1 000$, $1 ≤ R ≤ M$, $1 ≤ C ≤ N$.
 
h3. Soluţie:
 
...
 
h2(#problema-5). '5. Trans':problema/trans (ONI 2004)

bq. Se dau $N$ blocuri de piatră, de culoare albă sau neagră aşezate în ordinea $1$, $2$,.., $N$. Blocurile de piatră trebuie să fie transportate în ordinea în care sunt, iar pentru aceasta va trebui închiriat un camion. Se mai dau $Q$ tipuri de camioane. Camionul de tipul $i (1 ≤ i ≤ Q)$ poate transporta maxim $K{~i~}$ blocuri de piatră la un moment dat şi pentru un transport se percepe taxa $T{~i~}$. Se impune condiţia ca toate blocurile de piatră plasate în camion la un transport sa aibă aceeaşi culoare. Aşadar, pentru a fi transportate toate blocurile, se va alege un camion de un anumit tip, iar camionul va efectua unul sau mai multe transporturi. Pentru a micşora suma totală plătită, există posibilitatea de a schimba culoarea oricărui bloc de piatră (din alb în negru sau din negru în alb); pentru fiecare bloc $i (1 ≤ i ≤ N)$ se cunoaşte suma $S{~i~}$ ce trebuie plătită pentru a-i schimba culoarea $C{~i~}$.
Cerinţă: Pentru fiecare dintre cele $Q$ tipuri de camioane, determinaţi suma minimă plătită pentru a transporta toate cele $N$ blocuri.

}
==

h2(#problema-5). '5. Otilia':problema/otilia  (.campion)

h2(#problema-6). '6. Otilia':problema/otilia  (.campion, 2005)

bq. Otilia şi Burbucel au o grămadă de $N$ pietre şi vor juca un joc cu următoarele trei reguli: 1. Primul jucător are voie să ia din gramadă cel mult $K$ piese; 2. Cu excepţia primei mutări, fiecare jucător are voie să ia maxim $P * t$ pietre, unde $t$ este numărul de pietre care au fost substituite din grămadă la mutarea precedentă; 3. Pierde cel care mută ultimul (cel care ia ultimele pietre din grămadă).
Cerinţă: Se dau $M$ jocuri prin numerele $N$, $K$ şi $P$. Se cere să se determină dacă Otilia va câştiga fiecare din jocuri sau nu.

Este evident că prima relaţie o implică pe cea de-a doua. În momentul acesta se poate construi următorul algoritm: având lista de poziţii care pot fi bune pentru $X$ (sortată descrescător) o căutăm pe cea mai mare ca valoare care este într-adevăr bună. În principiu, scoatem din capul listei poziţiile rele până când dăm de o poziţie bună. La listă se va adăuga şi $X$ şi se va trece la pasul următor. Operaţiile algoritmului sunt chiar operaţiile asupra unui deque.

h2(#problema-6). '6. Bcrc':problema/bcrc (Stelele Informaticii)

h2(#problema-7). '7. Bcrc':problema/bcrc (Stelele Informaticii, 2006)

bq. Se consideră $N$ camere, numerotate de la $1$ la $N$, aşezate în cerc. Iniţial (la momentul de timp 0), ne aflăm în camera $1$. În fiecare moment de timp, putem alege să rămânem în camera în care ne aflăm sau să ne deplasăm într-o cameră vecină într-o unitate de timp. Se dă o listă de $M$ cutii ce conţin bomboane prin $T$, $C$ şi $B$: cutia apare la momentul $T$ în camera $C$ şi conţine $B$ bomboane. Cutia va dispărea la momentul $T + 1$.
Cerinţă: Cunoscând numărul de camere din labirint şi momentele de timp la care apar cutiile cu bomboane, determinaţi care este numărul maxim de bomboane pe care le putem culege.

Complexitatea finală: <tex> O(M * N) </tex>.

h2(#problema-7). '7. Cut the Sequence':http://acm.pku.edu.cn/JudgeOnline/problem?id=3017 (PKU)

h2(#problema-8). '8. Cut the Sequence':http://acm.pku.edu.cn/JudgeOnline/problem?id=3017 (PKU)

bq. Se dă o secvenţă $S$ de numere întregi de lungime $N$. Va trebui să se împartă secvenţa în mai multe subsecvenţe astfel încât suma valorilor din fiecare parte să nu depăşească un număr întreg $M$ dat, iar dacă însumăm maximul din fiecare subsecvenţă să obţinem o sumă cât mai mică.
Restricţii: $0 < N ≤ 100 000$, $0 ≤ S{~i~} ≤ 1 000 000$.