| 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
Tyrant's eye 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.
Tyrant's eye 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, pe primul rând, numărul T de teste in fişier. Urmează T perechi de rânduri, fiecare descriind câte un scenariu de test. 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 T rânduri. Fiecare rând va conţine răspunsul pentru un test, mai exact valorile K şi P cerute.
Restricţii
- 1 ≤ N ≤ 300.000.
- 0 ≤ v[i] ≤ 109.
- 1 ≤ T ≤ 10.
- Suma valorilor lui N într-un fişier este cel mult 300.000.
- Pentru 10 puncte, K = 1.
- Pentru alte 10 puncte, K ≤ 2.
- Pentru alte 10 puncte, K ≤ 15, v[i] ≤ 1.
- Pentru alte 50 de puncte, N ≤ 1.000.
Exemplu
| kxorbonacci.in | kxorbonacci.out |
|---|---|
| 3 5 1 0 1 1 0 5 1 2 3 1 2 5 0 0 0 0 0 | 2 1 2 1 1 1 |
Explicaţie
Pentru primul test, K = 2 şi a[1] = 1, a[2] = 0. Dacă aplicam regula din enunţ pentru a calcula următorile valori din a, deducem că a[3] = a[1] xor a[2] = 1 xor 0 = 1, a[4] = a[2] xor a[3] = 0 xor 1 = 1, a[5] = a[3] xor a[4] = 1 xor 1 = 0. Astfel vedem că v se regăseşte în a începând la poziţia P = 1.
