Revizia anterioară Revizia următoare
| 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
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 = (x1, x2, ... xk) de numere intregi. Pornind de la elementul X, primul element al sirului, Gigel aduna x1 pentru a obtine cel de-al doilea element al sirului, apoi la al doilea element al sirului aduna x2 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 x1, 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.
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.
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 = (x1, x2, ... xk).
Restrictii
- 5 ≤ N ≤ 100 000
- Numerele din sirul dat de Gigel se incadreaza intotdeauna in intregi cu semn pe 64 de biti
Exemplu
| reguli.in | reguli.out |
|---|---|
| 7 8 10 14 13 15 19 18 | 3 2 4 -1 |
Explicatie
2, 4, -1
