kxorbonacci

Kxorbonacci

h2. 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]$.

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]$.

h2. Date de ieşire

În fişierul de ieşire $kxorbonacci.out$ se vor afişa valorile $K$ şi $P$ cerute.

Î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.

h2. Restricţii

* $1 ≤ N ≤ 1.000.000$.
* $1 ≤ v[i] ≤ 10^9^$.

* $1 ≤ N ≤ 300.000$.
* $0 ≤ v[i] ≤ 10^9^$.
* $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$.

h2. Exemplu
table(example). |_. kxorbonacci.in |_. kxorbonacci.out |

| 5

| 3
5

1 0 1 1 0

| 2 1 |

5
1 2 3 1 2
5
0 0 0 0 0
| 2 1
2 1
1 1|

h3. Explicaţie

Pentru acest 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$.

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$.

== include(page="template/taskfooter" task_id="kxorbonacci") ==