시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 161 | 26 | 20 | 15.267% |
Consider integer points on the $x$-axis. Every point with an $x$-coordinate of $1$ or greater is associated with one of the colors: red or black. Specifically, as shown in Figure D.1, the color of the point with the $x$-coordinate of $1$ is red, the next two points are black, the next three points are red, the next four points are black, and so on. In this way, every point with an $x$-coordinate of $1$ or greater is associated with either red or black color.
Figure D.1 Colors of points on the $x$-axis
Let $c(x)$ denote the color of the point with coordinate $x$($≥ 1$). Then $c(x)$ is defined as follows.
$$ c(x) = \begin{cases} \text{red,} & \text{if} \displaystyle\sum_{i=0}^{2k}{i} < x \le \displaystyle\sum_{i=0}^{2k+1}{i}&\text{for }k = 0, 1, 2, \dots \\ \text{black,} & \text{otherwise} \end{cases} $$
There are $n$ flags at given points along the $x$-axis. For example, Figure D.2 shows a situation where five flags are erected. The $x$-coordinates of the $n$ flags are denoted as $f_1$, $f_2$, $\dots$, $f_n$.
Figure D.2 An example of five flags on the $x$-axis
Displeased that the colors of points where flags locate are not the same, Bob tries to move all the flags to the right the same distance, say $d$, so that all the flags locate on the red points. In other words, he wants to find $d$ such that for every $i$($1 ≤ i ≤ n$), $c(f_i + d)$ is red.
Given information about the locations of $n$ flags, write a program to find the smallest possible value of $d$.
Your program is to read from standard input. The input starts with a line containing an integer $n$ ($1 ≤ n ≤ 10^5$), where $n$ is the number of flags. Each of the next $n$ lines contains an $x$-coordinate in increasing order. The $i$-th line contains $f_i$ ($1 ≤ i ≤ n$, $1 ≤ f_i ≤ 10^6$), the $x$-coordinate of the $i$-th flag
Your program is to write to standard output. Print exactly one line. The line should contain the minimum distance $d$ by which all the flags must move to the right so that all the flags are on the red points.
1 8
3
5 4 15 28 60 211
0
7 123 129 130 188 189 190 191
23