reguli

Reguli

== 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 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:

== include(page="template/badtests") ==

%{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$}.

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{~1~}, a{~2~}, ... a{~K~})$}. Pe baza primului element al sirului, {$x{~0~}$}, si al vectorului {$a$}, sirul {$x$} este unic determinat prin relatia de recurenta:
 
%{$x{~i~}$} = {$x{~i-1~} + a{~i mod K~}$}%, daca {$i mod K$} este diferit de {$0$}, sau
%{$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$}.

h2. Date de iesire

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~}.

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$}

* {$5 ≤ N ≤ 500 000$}

* Primele $N$ numere din sirul {$x$} se incadreaza intotdeauna in intregi cu semn pe 64 de biti
h2. Exemplu

== include(page="template/taskfooter" task_id="reguli") ==

1561