==Include(page="template/preoni-2007")==

_Comentarii aici..._
 

h1. Solutii Runda Finala
h2. 'Orase':problema/orase

h3. (problema medie, clasa a 9-a)

Vom calcula intai numarul de posibilitati pentru cazul in care $1$ se afla in unul din colturi. Sa presupunem ca l-am asezat in coltul stanga sus. Distingem doua cazuri:
 
* $2$ este asezat la dreapta lui $1$ caz in care exista un singur mod de completare
 
table(example). | 1 | 2 | 3 | ... |
| 2N | 2N-1 | 2N-2 | ... |
 
* $2$ este asezat in coltul dreapta jos caz in care vom avea de completat tabla ramasa cu numerele {$3$}, {$4$}, ... {$2N$} punand $3$ la dreapta lui $2$ lucru care este echivalent cu completarea unei table cu $N-1$ coloane cu $1$ fixat in unul din colturi.
 
table(example). | 1 |   | ... |
| 2 | 3 | ... |
 
In concluzie numarul de moduri in care se poate completa tabla de dimensiune $N$ cu $1$ pus intr-un colt fixat este {$N$}. Analizam acum cazul in care $1$ este pus pe una din coloanele {$2, 3 , ... N-1$}. $2$ nu poate fi pus sub $1$ deoarece tabla s-ar imparti in doua bucati care nu sunt conexe si nu se poate completa comform cerintei. Daca 2 este pozitionat in stanga lui 1 toate coloanele {$1, 2, ... i$} se vor completa in mod unic.
 
table(example). |i | ... | 2 | 1 | ... |
| i+1 | ... | 2*i - 1  | 2*i | ... |
 
Deci vor ramane de completat N-i coloane care trebuie completate cu 2*i+1 pus intr-un colt fixat. Deci vom avea in total N-i posibilitati. In mod analog daca $2$ se afla in dreapta vom avea $i-1$ posibilitati. Numarul total de posibilitati cand $1$ se afla pe una din coloanele {$2, 3, ... N-1$} va fi suma de la $2$ la $N-1$ din {$2(N-i+i-1)$} adica {$2(N-2)(N-1)$} deoarece se poate incepe de sus sau de jos. Raspunsul cautat va fi {$4N + 2(N-1)(N-2)$}, {$N > 1$}. Operatiile trebuiau efectuate pe numere mari.
 

h2. 'Sate':problema/sate
h3. (problema grea, clasa a 9-a, problema usoara, clasa a 10-a)

h3. (problema medie, clasa a 10-a)

Aceasta problema se rezolva folosind metoda programarii dinamice. O solutie triviala are complexitatea $O(N*T)$ si se realizeaza calculand vectorul $m[i] = costul minim pentru a obtine un kg de branza in saptamana i$. Acesta se obtine folosind formula $m[i] = min{C[j] + (i-j)*S | i-j ≤ T}$.
Pentru a reduce complexitatea la $O(N)$ se observa ca pentru calculul lui $m[i]$ avem nevoie doar de valorile lui $C$ cuprinse intre $max(1, i-T)$ si $i$, interval a carei dimensiuni nu poate decat sa creasca sau sa ramana constanta. Se foloseste un deque in care se introduc pe rand valorile din $C$ modificate corespunzator pentru a asigura gasirea minimului cerut la fiecare pas. Astfel la pasul $i$ se va introduce in deque valoarea $C[i] + (N-i)*S$, pentru a mentine relatia de ordine corespunzatoare relatiei de recurenta intre elementele structurii. La pasul $i$ se considera elementul din coada deque-ului (fie acela provenit de la $C[j]$) din care se scade @(N-j)*S@ pentru a obtine pe $m[i]$.
Solutia ceruta este @m[1]@ $* P{~1~} +$ @m[2]@ $* P{~2~} + ... + m[N] * P{~N~}$
 

h2. 'Gradina':problema/gradina
h3. (problema grea, clasa a 10-a)