h2. 'Biomech':problema/biomech

Vom calcula matricea $A[lstart][dirstart][lfinish][dirfinish][P]$, reprezentand timpul minim pentru a ajunge de pe linia $lstart$, o coloana oarecare $X$ si privind in directia $distart$, pana pe linia $lfinish$, coloana $X + 2^P^$ (deci o coloana situata cu $2^P^$ pozitii in dreapta) si privind in directia $dirfinish$. Pentru $P = 0$, vom folosi un algoritm de drum minim. Va trebui sa avem grija ca solutia de timp minim pentru a trece de pe o coloana pe coloana imediat din dreapta ei poate presupune niste mutari "in spate", pe un numar limitat de coloane din stanga. Alegand o limita maxima de $9$ coloane in stanga si in dreapta, putem folosi algoritmul Dijkstra pe un graf ale carui stari constau din elementele unei submatrici de $5$ linii, $19$ coloane si au $8$ orientari. Pentru $P > 0$, $A[lstart][dirstart][lfinish][dirfinish][P]=A[lstart][dirstart][lintermed][dirintermed][P-1] + A[lintermed][dirintermed][lfinish][dirfinish][P-1]$. Variem linia si orientarea intermediara si pastram minimul. In mod similar, vom calcula o matrice $B[lstart][dirstart][lfinish][dirfinish][P]$, unde indicele $P$ va reprezenta sosirea pe o coloana situata cu $2^P^$ coloane la stanga coloanei de start.
 
Cu aceste matrici calculate, vom determina numarul maxim de coloane pe care le poate parcurge robotul  spre stanga si spre dreapta, in timpul dat, alegand maximul dintre cele $2$ variante. Voi prezenta in continuare doar cazul deplasarii spre dreapta, cel al deplasarii spre stanga fiind similar. Vom porni de la coloana $0$ si vom mari treptat numarul de coloane pe care le poate parcurge robotul (fie acest numar $C$). Pentru fiecare valoare a lui $C$ si fiecare stare posibila $(linie,orientare)$ vom mentine timpul minim in care se poate ajunge in stares respectiva. Initial, robotul poate ajunge in $0$ unitati de timp doar in starea initiala, in celelalte stari el neputand ajunge. Vom porni cu $P$ de la valoarea maxima pentru care am calculat valori (de exemplu, aceasta valoare poate fi $61$) si il vom decrementa treptat. Presupunand ca am ajuns pana la coloana $C$, vom incerca acum sa parcurgem inca $2^P^$ coloane. Folosind matricea $A$ si cunoscand timpul minim pentru a ajunge la coloana $C$ in fiecare stare posibila, vom calcula timpul minim corespunzator fiecarei stari pentru a ajunge la coloana $C+2^P^$. Daca cel putin o stare are acest moment de timp mai mic sau egal cu durata de timp maxim data, atunci incrementam valoarea lui $C$ si vom considera momentele de timp actualizate pentru noua valoare a lui $C$. Daca pentru nici o stare nu se poate ajunge la coloana $C+2^P^$ in timp util, atunci lasam valoare lui $C$ nemodificata, nefacand nimic altceva (la urmatorul pas avand, insa, o valoare a lui $P$ cu $1$ mai mica). Valoarea finala a lui $C$ este numarul maxim de coloane ce poate fi parcurs spre dreapta in timpul dat.
 

h2. 'Expresii min-max':problema/emm
Expresia data poate fi evaluata folosind o metoda de complexitate liniara ({$O(N)$}). Pentru simplificarea explicatiilor, vom considera ca intreaga expresie este incadrata intr-o pereche de paranteze. Se parcurge expresia de la stanga la dreapta si se va mentine o stiva cu operatorii neevaluati inca, cu rezultate partiale si cu paranteze deschise. Cand se inalneste un operator, acesta se adauga in stiva. Cand se intalneste un operand si in varful stivei este un operator, se efectueaza operatia respectiva (caci in stiva se va gasi si cel de-al doilea operand): adica se elimina din stiva operatorul si cel de-al doilea operand si se pune in varful stivei rezultatul operatiei. Cand se intalneste un operand si in stiva se afla o paranteza deschisa, operandul se pune in varful stivei. La intalnirea unei paranteze inchise vom evalua toate operatiile pana la prima paranteza deschisa din stiva. Apoi vom inlocui paranteza deschisa cu rezultatul evaluarii si, daca pe nivelul urmator din stiva se gaseste un operator, atunci efectuam operatia. La final, in varful stivei vom avea rezultatul expresiei.