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

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

h1. Solutii Runda 2
h2. 'Amlei':problema/amlei

h3. (problema usoara, clasele 11-12)

Problema se rezolva folosind cunostinte de potrivire a sirurilor. Fie sirul $D$ sirul diferentelor dintre termeni consecutivi ai sirului {$x$}. Astfel, trebuie sa determinam cea mai scurta perioada a acestui sir. Pentru a calcula aceasta informatie in {$O(N)$}, vom calcula functia prefix corespunzatoare sirului conform algoritmului de potrivire Knuth-Morris-Prat (KMP). Avand aceasta functie calculata, putem determina in {$O(1)$} daca primele $L$ elemente din $D$ reprezinta o perioada astfel: fie $r$ restul impartirii lui $N$ la {$L$} ( cate elemente raman la sfarsit intr-o posibila perioada incompleta ) si $c$ catul acestui rest ( numarul de perioade ). $L$ poate fi deci lungimea unei perioade daca si numai daca sunt indeplinite simultan conditiile:
 
* PI{~N-r~} > 0
* {$(N-r)$} divizibil la {$(N-r-PI{~N-r~})$}
* {$(N-r)$} / {$(N-r-PI{~N-r~})$} = $c$,
 
unde PI{~i~} este vectorul reprezentat de functia prefix.
 
Dintre toate lungimile $L$ care indeplinesc conditiile de mai sus se alege cea care are lungimea minima. Aceasta abordare nu este unica abordare optima. Algoritmul mentionat obtine 100 de puncte.
 

h2. 'Ghiozdan':problema/ghiozdan
h3. (problema grea, clasele 11-12)