Fişierul intrare/ieşire:	reguli.in, reguli.out	Sursă	preONI 2007, Runda 2
Autor	Filip Cristian Buruiana	Adăugată de	Filip Cristian Buruiana •filipb
Timp execuţie pe test	0.175 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	3/5

Vezi solutiile trimise | Statistici

Reguli

Testele pentru aceasta problema nu sunt destul de bine construite pentru a departaja corect solutii ineficiente sau gresite. Intra aici daca vrei sa ne ajuti sa imbunatatim calitatea testelor pentru aceasta problema!

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₂, ... a_K). Pe baza primului element al sirului, x₀, 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.

Gigel noteaza intr-un carnet primele N elemente ale sirului x, x₀, x₁, ... 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?

Date de intrare

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.

Date de iesire

Pe prima linie a fisierului reguli.out se afla K, lungimea minima a unui vector (a₁, a₂, ... 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.

Restrictii

• 5 ≤ N ≤ 500 000
• Primele N numere din sirul x se incadreaza intotdeauna in intregi cu semn pe 64 de biti

Exemplu

Explicatie

Cea mai scurta regula determinata este 2, 4, -1. Se obtin astfel elementele:
x₁ = x₀ + a₁ = 8 + 2 = 10
x₂ = x₁ + a₂ = 10 + 4 = 14
x₃ = x₂ + a₃ = 14 + (-1) = 13
x₄ = x₃ + a₁ = 13 + 2 = 15
x₅ = x₄ + a₂ = 15 + 4 = 19
x₆ = x₅ + a₃ = 19 + (-1) = 18
x₇ = x₆ + a₁ = 18 + 2 = 20

Cum se trimit solutii?