==Include(page="template/monthly-2014")==

h1. Solutii Infoarena Monthly 2014 - Runda 3

h1. 'Bancomat':problema/bancomat

(toc)*{text-align:center} *Lista de probleme*
* 'Beep':algoritmiada-2014/runda-3/solutii#beep
* 'Bancomat':algoritmiada-2014/runda-3/solutii#bancomat
* 'Basequery':algoritmiada-2014/runda-3/solutii#basequery
* 'Concert2':algoritmiada-2014/runda-3/solutii#concert2

Bancnotele de valori mici vor fi păstrate pentru a "completa" suma cerută de un client. Mai exact, dacă un client doreşte să extragă $364$ de bani din bancomat, suma de $4$ bani poate fi obţinută doar din bancnote de $1$ ban. Intuitiv, trebuie să păstrăm bancnotele cu valoare mică pentru rezolvarea acestor cazuri. Vom oferi suma de bani cerută de fiecare client în parte în mod optim, folosind monedele, în ordinea descrescătoare a valorii acestora. Vom "umple" fiecare sumă de bani $X$ mai întâi cu bancnote de $500$ lei, apoi de $100$ lei, $50$ lei, etc. Dacă nu putem să oferim suma cerută de un om, vom returna $NU$.

==include(page="monthly-2014/runda-3/solutii/beep")==

h1. 'Basequery':problema/basequery

==include(page="monthly-2014/runda-3/solutii/bancomat")==

Vom transforma fiecare număr din şir în toate bazele de numeraţie între $2$ şi $16$. Pentru fiecare număr astfel obţinut, vom parcurge toate secvenţele care au valoarea din baza $10$ mai mică decât $1024$, folosind doi indici. Pentru fiecare astfel de secvenţă, vom reţine baza în care este scrisă, lungimea acesteia şi valoarea ei din baza $10$. Deci, de fiecare dată când dăm peste o secvenţă de lungime $L$, scrisă în baza $B$, cu valoarea $X$ în baza $10$, vom adăuga într-o sumă asociată acestor $3$ stări $X$. Vom construi astfel o structură tridimensională cu următoarea semnificaţie:

==include(page="monthly-2014/runda-3/solutii/basequery")==

* $d[base][length][val] = C( A ~i~, P, B ) * A ~i~$
 
Astfel, pentru fiecare întrebare din cele $Q$, vom transforma secvenţa $P$, de lungime $L$ din baza $B$ în baza $10$, reţinând şi valoarea acesteia. Rămâne să afişăm valoarea reţinută în structura construită mai sus.
 
h1. 'Beep':problema/beep
 
Vom citi cuvântul interzis. Vom citi apoi fiecare cuvânt în parte din textul care trebuie corectat. Comparăm fiecare cuvânt citit cu cel interzis. Dacă sunt egale, vom afişa "beep". În caz contrar, vom afişa chiar cuvântul citit.
 
h1. 'Concert2':problema/concert2
 
Problema se rezolva cu ajutorul programarii dinamice:
 
* $dp[i][j][p]$ = lungimea maxima a unui subsir care respecta proprietatile din enunt si se termina pe pozitia $i$ iar ultima secventa crescatoare are lungimea $j$ pentru $p = 0$ si lungimea maxima a unui subsir care respecta proprietatile din enunt si se termina pe pozitia $i$ iar ultima secventa descrescatoare are lungimea $j$ pentru $p = 1$.
 
O recurenta in $O(N)$ nu se incadreaza in timp, de aceea va trebui sa construim $2*K$ arbori de intervale pentru a putea calcula in timp logaritmic maximul pe un interval.Pentru asta este necesar sa normalizam datele de intrare. Solutia se gaseste in maximul din aceasta matrice.
 
Complexitate : $O(N * logN *K)$
 
==include(page="template/monthly-2014/footer")==

==include(page="monthly-2014/runda-3/solutii/concert2")==