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

_Comentarii aici..._
 

h1. Solutii Runda Finala
h2. 'Orase':problema/orase
h3. (problema usoara, clasa a 9-a)

La primul pas se vor sorta orasele crescator dupa $D{~i~}$. Renumerotand orasele in ordinea sortarii, putem calcula distanta care trebuie parcursa intre doua orase $i < j$: $L{~i~}+D{~i~}+L{~j~}-D{~j~}$. Pentru fiecare $i$ vrem sa determinam un oras $j < i$ astfel incat sa se maximizeze aceasta distanta. Alegerea optima va fi un oras $j$ cu valoarea $L{~j~}-D{~j~}$ maxima; astfel, pe masura ce se avanseaza cu indicele $i$ se pastreaza si un indice $j$ maxim pana in prezent. Complexitatea rezolvarii este $O(N*lg N)$ datorita sortarii.

La primul pas se vor sorta orasele crescator dupa $D{~i~}$. Renumerotand orasele in ordinea sortarii, putem calcula distanta care trebuie parcursa intre doua orase $j < i$: $L{~i~}+D{~i~}+L{~j~}-D{~j~}$. Pentru fiecare $i$ vrem sa determinam un oras $j < i$ astfel incat sa se maximizeze aceasta distanta. Alegerea optima va fi un oras $j$ cu valoarea $L{~j~}-D{~j~}$ maxima; astfel, pe masura ce se avanseaza cu indicele $i$ se pastreaza si un indice $j$ maxim pana in prezent. Complexitatea rezolvarii este $O(N*lg N)$ datorita sortarii.

h2. 'Sarpe':problema/sarpe

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.

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