Fişierul intrare/ieşire:reguli.in, reguli.outSursăpreONI 2007, Runda 2
AutorFilip Cristian BuruianaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.35 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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 (a1, a2, ... aK). Pe baza primului element al sirului, x0, si al vectorului a, sirul x este unic determinat prin relatia de recurenta:

xi = xi-1 + ai mod K, daca i mod K este diferit de 0, sau
xi = xi-1 + aK, 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, x0, x1, ... xN-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 xi-1.

Date de iesire

Pe prima linie a fisierului reguli.out se afla K, lungimea minima a unui vector (a1, a2, ... ak) ce poate genera primele N elemente ale sirului x. Urmeaza K linii ce descriu vectorul determinat, pe linia i+1 aflandu-se ai.

Restrictii

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

Exemplu

reguli.inreguli.out
8
8
10
14
13
15
19
18
20
3
2
4
-1

Explicatie

Cea mai scurta regula determinata este 2, 4, -1. Se obtin astfel elementele:
x1 = x0 + a1 = 8 + 2 = 10
x2 = x1 + a2 = 10 + 4 = 14
x3 = x2 + a3 = 14 + (-1) = 13
x4 = x3 + a1 = 13 + 2 = 15
x5 = x4 + a2 = 15 + 4 = 19
x6 = x5 + a3 = 19 + (-1) = 18
x7 = x6 + a1 = 18 + 2 = 20

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content