== include(page="template/taskheader" task_id="reguli") ==
La ora de matematica, Gigel invata despre siruri. Pentru a intelege mai bine cum functioneaza acestea, el incearca mai intai sa construiasca niste siruri speciale astfel: alege un element $X$ care il considera ca fiind primul termen al sirului si afla apoi toate elementele sale urmarind niste reguli stabilite anterior. O regula pentru un sir este un vector {$x$} = {$(x{~1~}, x{~2~}, ... x{~k~})$} de numere intregi. Pornind de la elementul {$X$}, primul element al sirului, Gigel aduna {$x{~1~}$} pentru a obtine cel de-al doilea element al sirului, apoi la al doilea element al sirului aduna {$x{~2~}$} pentru a obtine cel de-al treilea element, etc. Dupa ce a utilizat toate cele $k$ numere, procedeul se repeta: la ultimul numar obtinut se aduna {$x{~1~}$}, etc.
Gigel construieste un sir de lungime $N$ folosind procedeul de mai sus. Problema apare cand, dupa un timp, el uita regula pe care a folosit-o pentru a-l genera. Sa se determine cea mai scurta regula care a generat sirului respectiv.
La ora de matematica, Gigel invata despre siruri. Pentru a intelege mai bine cum functioneaza acestea, el incearca mai intai sa construiasca niste siruri speciale pe baza anumitor criterii, siruri ce au ca termeni numai numere intregi. O regula {$a$} pentru un sir {$x$} este un vector {$a$} = {$(a{~1~}, a{~2~}, ... a{~k~})$} de numere intregi. Pe baza primului element al sirului, {$x{~0~}$}, si al acestui vector, sirul {$x$} este unic determinat prin relatia de recurenta:
%{font-size:14px}{$x{~i~}$} = {$x{~i-1~} + a{~i mod K~}$}% , daca {$i mod K$} este diferit de {$0$}, si
%{font-size:14px}{$x{~i~}$} = {$x{~i-1~} + a{~k~}$}% , daca {$i mod K$} este {$0$}.
Prin {$A mod B$} se intelege restul impartirii lui numarului {$A$} la {$B$}.
Gigel noteaza intr-un carnet primele $N$ elemente ale sirului {$x$}, {$x{~0~}, x{~1~}, ... x{~N-1~}$}, sir obtinut conform procedeului de mai sus. Bineinteles, dupa un timp, dupa ce Gigel uita regula pe care a folosit-o pentru a obtine sirul de pe carnet, apar intrebarile. Care este cel mai scurt vector {$a$} ( ca numar de elemente ), conform caruia se pot obtine primele $N$ elemente ale sirului {$x$}?
h2. Date de intrare
Fisierul de intrare este {$reguli.in$}. Pe prima linie a acestui fisier se afla {$N$}, numarul de elemente al sirului pe care ni le da Gigel (primele {$N$} elemente de fapt, pentru ca un sir este infinit). Urmatoarele $N$ linii contin cate un numar intreg.
Fisierul de intrare este {$reguli.in$}. Pe prima linie a acestui fisier se afla {$N$}. Urmatoarele $N$ linii contin cate un numar intreg, pe linia {$i+1$} aflandu-se valoarea elementului {$x{~i-1~}$}.
h2. Date de iesire
Pe prima linie a fisierului {$reguli.out$} se afla {$K$}, lungimea minima a unei reguli ce poate duce la sirul din fisierul de intrare. Urmeaza {$K$} linii, pe fiecare aflandu-se cate un numar intreg, descriind regula determinata sub forma vectorului {$x$} = {$(x{~1~}, x{~2~}, ... x{~k~})$}.
Pe prima linie a fisierului {$reguli.out$} se afla {$K$}, lungimea minima a unui vector {$(a{~1~}, a{~2~}, ... a{~k~})$} ce poate genera primele {$N$} elemente ale sirului {$x$}. Urmeaza {$K$} linii ce descriu vectorul determinat, pe linia $i+1$ aflandu-se a{~i~}.
h2. Restrictii
* {$5 ≤ N ≤ 100 000$}
* Numerele din sirul dat de Gigel se incadreaza intotdeauna in intregi cu semn pe 64 de biti
* Primele $N$ numere din sirul {$x$} se incadreaza intotdeauna in intregi cu semn pe 64 de biti
h2. Exemplu
table(example). |_. reguli.in |_. reguli.out |
|7
|8
8
10
14
