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.
Restricţii: $1 ≤ M ≤ 30 000$, $1 ≤ N ≤ 5 000 000$, $1 ≤ K ≤ N$, $1 ≤ P ≤ 10$.

Cerinţă: Se dau $M$ jocuri prin numerele $N$, $K$ şi $P$. Se cere să se determine pentru fiecare joc dacă Otilia va câştiga sau nu.
Restricţii: $1 ≤ M ≤ 30.000$, $1 ≤ N ≤ 5.000.000$, $1 ≤ K ≤ N$, $1 ≤ P ≤ 10$.

h3. Soluţie (Silviu Ganceanu):

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.

Restricţii: $3 ≤ N ≤ 2 048$, $0 ≤ M ≤ 50 000$, $1 ≤ T ≤ 1 000 000 000$, $1 ≤ C ≤ N$, $1 ≤ B ≤ 9 999$.

Restricţii: $3 ≤ N ≤ 2.048$, $0 ≤ M ≤ 50.000$, $1 ≤ T ≤ 1.000.000.000$, $1 ≤ C ≤ N$, $1 ≤ B ≤ 9.999$.

h3. Soluţie:
Soluţia foloseşte metoda programării dinamice.

O stare se reprezintă prin camera în care ne aflăm şi momentul de timp. Fie <tex> bst_{i,j} </tex> numărul maxim de bomboane culese până în momentul <tex> i </tex> când ne găsim în camera <tex> j </tex>. O observaţie evidentă este că <tex> bst_{i,j} </tex> se poate modifica doar în momentele în care apar cutiile. Prin urmare, vom considera momentele de timp când apar cutiile, momente ce sunt în număr de <tex> M </tex>, <tex> bst_{i,j} </tex> însemnând numărul maxim de bomboane culese ştiind că ne aflăm în camera <tex> j </tex> unde am cules cutia <tex> i </tex>. De cine depinde această stare? Ştim că <tex> bst_{i-1,1 \ldots N} </tex> a fost deja calculat în mod optim. Să notăm cu <tex> T </tex> diferenţa de timp dintre momentele la care apare cutia <tex> i </tex> şi cutia <tex> i - 1 </tex>. În această stare, <tex> i </tex> şi cameră <tex> j </tex>, putem ajunge din maxim <tex> T </tex> camere spre stânga sau spre dreapta, întrucât fiecare deplasare între două camere costă o unitate de timp. De unde deducem că:

O stare se reprezintă prin camera în care ne aflăm şi momentul de timp. Fie <tex> bst_{i,j} </tex> numărul maxim de bomboane culese până în momentul <tex> i </tex> când ne găsim în camera <tex> j </tex>. O observaţie evidentă este că <tex> bst_{i,j} </tex> se poate modifica doar în momentele în care apar cutiile. Prin urmare, vom considera momentele de timp când apar cutiile, momente ce sunt în număr de <tex> M </tex>, <tex> bst_{i,j} </tex> însemnând numărul maxim de bomboane culese ştiind că ne aflăm în camera <tex> j </tex> după ce am cules cutia <tex> i </tex>. De cine depinde această stare? Ştim că <tex> bst_{i-1,1 \ldots N} </tex> a fost deja calculat în mod optim. Să notăm cu <tex> T </tex> diferenţa de timp dintre momentele la care apar cutia <tex> i </tex> şi cutia <tex> i - 1 </tex>. În această stare, cutie <tex> i </tex> şi cameră <tex> j </tex>, putem ajunge din maxim <tex> T </tex> camere spre stânga sau spre dreapta, întrucât fiecare deplasare între două camere costă o unitate de timp. De unde deducem că:

* <tex> bst_{i,j} = Min\{\ bst_{i-1,j-T},\ bst_{i-1,j-T+1}, \ldots,\ bst_{i-1,j}, \ldots,\ bst_{i-1,j+T-1},\ bst_{i-1,j+T}\ \}; </tex>

* <tex> bst_{i,j} = Max\{\ bst_{i-1,j-T},\ bst_{i-1,j-T+1}, \ldots,\ bst_{i-1,j}, \ldots,\ bst_{i-1,j+T-1},\ bst_{i-1,j+T}\ \}; </tex>

Metoda directă, şi aparent eficientă, constă în folosirea unui arbore de intervale pentru aflarea acestui minim. Însă, intervalul <tex> [j-T,j+T] </tex> se deplasează constant spre dreapta, dacă vom considera indicii <tex> j </tex> în ordine <tex> 1, 2, 3, \ldots </tex>. În acest interval noile elemente se introduc prin dreapta şi altele se elimină prin stânga. Însă, cum am arătat în problemele precedente, nu avem nevoie de toate valorile din acest interval. Şi din acest motiv vom folosi un deque de lungime <tex> T * 2 + 1 </tex> cu care vom elimina poziţiile care nu sunt candidate la soluţie. Mai jos este o reprezentare grafică a acestei explicaţii.

Metoda directă, şi aparent eficientă, constă în folosirea unui arbore de intervale pentru aflarea acestui maxim. Însă, intervalul <tex> [j-T,j+T] </tex> se deplasează constant spre dreapta, dacă vom considera indicii <tex> j </tex> în ordine <tex> 1, 2, 3, \ldots </tex>. În acest interval noile elemente se introduc prin dreapta şi altele se elimină prin stânga. Însă, cum am arătat în problemele precedente, nu avem nevoie de toate valorile din acest interval. Şi din acest motiv vom folosi un deque de lungime maximă <tex> T * 2 + 1 </tex> cu care vom elimina poziţiile care nu sunt candidate la soluţie. Mai jos este o reprezentare grafică a deplasării intervalului menţionate mai sus.

p=. !deque-si-aplicatii?bcrc.png 40%!