(Creat de '_ditzonec_':user/ditzonec la data de _2006-01-21_ categoria _Competitii_, autor(i) _Echipa info-arena_)
*Continut scurt:*

 ==Include(page="template/raw")==
 
Runda a 3-a concursului preONI 2006 s-a incheiat. Acest articol va prezinta solutiile oficiale ale celor 7 probleme propuse precum si cateva aprecieri pe marginea concursului.

 Runda a 3-a concursului preONI 2006 s-a incheiat. Acest articol va prezinta solutiile oficiale ale celor 7 probleme propuse precum si cateva aprecieri pe marginea concursului.

*Continut lung:*

==Include(page="template/raw")==
 

S-a incheiat si cea de-a treia runda a concursului preONI 2006. Ca de obicei, la fiecare grupa au existat 3 probleme cu nivele diferite de dificultate: usor, mediu, greu. Spre deosebire de runda precedenta, problemele au fost ceva mai accesibile facand mai usoara obtinerea unui punctaj mediu pentru participantii de la toate cele trei grupe. Salutam primul punctaj maxim realizat de Cosmin Gheorghe, participant la clasa a IX-a. Desi nivelul de dificultate al problemelor este unul ridicat (comparativ cu cel de la nationale), nu putem sa nu remarcam faptul ca, la clasa a X-a, nivelul de pregatire al concurentilor este ceva mai scazut fata de celelalte grupe, in conditiile in care olimpiadele se apropie. Ii sfatuim pe toti participantii sa se pregateasca si mai consistent de acum incolo, utilizand si platforma pe care le-o pune la dispozitie InfoArena.
Inainte de ultima runda, la clasa a IX-a, avem deja doi concurenti care s-au detasat de pluton in persoana lui Gheorghe Cosmin si Tataroiu Bogdan, lupta fiind inca acerba pentru ultimele locuri calificabile. La clasa a X-a avem un clasament destul de echilibrat, cu elevii clasati primii fara prea mari emotii inainte de ultima runda, dar cu multe semne de intrebare pentru cei clasati pe locurile 8-10. La clasele XI-XII avem o batalie frumoasa, cu multe punctaje peste 300 si o situatia foarte confuza catre ultimele locuri calificabile.

Problema se rezolva cu programare dinamica. Utilizam urmatoare structura de date:

* V[i][j][0] *C numarul de posibilitati pentru a pava i metri astfel incat primele j placi sa fie albe
* V[i][j][1] *C numarul de posibilitati pentru a pava i metri astfel incat primele j placi sa fie negre

* V[i][j][0] ¨C numarul de posibilitati pentru a pava i metri astfel incat primele j placi sa fie albe
* V[i][j][1] ¨C numarul de posibilitati pentru a pava i metri astfel incat primele j placi sa fie negre

Relatiile de recurenta sunt acum usor de dedus. Odata calculata matricea putem raspunde foarte usor primei cerinte, facand suma V[N][i][0] (pentru 1 <= i <= A) si V[N][i][1] pentru (1 <= i <= B).