Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | kxorbonacci.in, kxorbonacci.out | Sursă | Algoritmiada 2022, Runda 1 |
| Autor | Tamio-Vesa Nakajima | Adăugată de |  Botocan Cristian-Alexandru •Botzki17 |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Kxorbonacci
Komi a găsit, explorând nişte ruine magice, definiţia unui nou tip de şir, numit şirul mistic! Valorile şirului sunt a[1],..., iar şirul se consideră a fi infinit. Şirul mistic este determinat de primele K elemente a[1], ..., a[K]. Următoarele numere sunt egale cu xor-ul ultimelor K numere din şir. Astfel a[K+1] = a[1] xor ... xor a[K], şi a[K+2] = a[2] xor ... xor a[K+1], şi aşa mai departe.
Komi a reuşit până la urmă să găsească, adânc în ruină, un şir de N numere v[1], ..., v[N]. Ea ghiceşte că acest şir este o subsecvenţă a şirului mistic; adică, pentru o poziţie P, v[1] = a[P], v[2] = a[P+1], ..., v[N] = a[P+N-1]. Ea vrea acum să găsească pe K şi pe P. În cazul în care sunt mai multe soluţii posibile, să se găsească cea cu K minim; dacă tot sunt mai multe soluţii posibile, să se găsească cea cu P minim.
Date de intrare
Fişierul de intrare kxorbonacci.in conţine două rânduri. Primul rând conţine numărul N, al doilea rând conţine valorile $v[1], ..., v[N].
Date de ieşire
În fişierul de ieşire kxorbonacci.out se vor afişa valorile K şi P cerute.
Restricţii
- 1 ≤ N ≤ 1.000.000.
- 1 ≤ v[i] ≤ 109.
- Pentru 10 puncte, K = 1.
- Pentru alte 10 puncte, K ≤ 2.
- Pentru alte 10 puncte, v[i] ≤ 1.
- Pentru alte 50 de puncte, N ≤ 1.000.
Exemplu
| kxorbonacci.in | kxorbonacci.out |
|---|---|
| 5 1 0 1 1 0 | 2 1 |
Explicaţie
Pentru acest test, K = 2 şi a1 = 1, a2 = 0. Dacă aplicam regula din enunţ pentru a calcula următorile valori din a, deducem că a3 = a1 xor a2 = 1 xor 0 = 1, a4 = a2 xor a3 = 0 xor 1 = 1, a5 = a3 xor a4 = 1 xor 1 = 0. Astfel vedem că v se regăseşte în a începând la poziţia P = 1.
