시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 4 | 3 | 3 | 75.000% |
Consider an array $A$ of length $N$. The instability of $A$ is defined as $$\sum\limits_{i = 1}^{N - 1} (|A[i + 1] - A[i]|)\text{.}$$
Master Zhu wants to stabilize an array. In order to do that, he wants to select an integer $X$ and change every element $A[i]$ to $(A[i] \oplus X)$. Here, $u \oplus v$ is the bitwise XOR of $u$ and $v$.
Find the smallest non-negative integer $X$ Master Zhu must choose to minimize the instability of a given array, and calculate the resulting instability.
The first line of input contains an integer $N$ ($1 \le N \le 10^5$). Next line contains $N$ integers $A[i]$, indicating the elements of the array ($0 \le A[i] < 2^{20}$).
Print a single line containing two integers: the smallest non-negative integer $X$ which must be used in order to reach the minimum possible instability and the resulting instability itself.
3 0 3 0
1 2
3 1 3 1
0 4