| 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 (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.in | reguli.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
