• Infoarena Monthly 2014
• Format
• Clasament
• Organizatori
• Sponsori si premii
• Regulament
•  
• Runda 1
• Runda 2
• Runda 3
• Runda 4
• Runda 5
• Runda 6
• Runda 7
• Runda 8
• Runda 9
• Runda 10
• Runda 11
• Runda 12

Bancomat

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.

Basequery

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:

• 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.

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.

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)