No.1925 Evil Spirit Minajigen
Problem Statement
Chased by the evil spirit Minajigen, YUKI has strayed into the first dimension and is trying to defect to the zeroth dimension. However, only unicellular organisms can live in the zeroth dimension.
YUKI has cell walls at $x_1, x_2, \ldots, x_{N+1}$ (in ascending order). YUKI's cells are the minimal intervals containing two cell walls; there are $N$ of them: $[x_1, x_2], [x_2, x_3], \ldots, [x_N, x_{N+1}]$.
Until only one cell remains, YUKI and Minajigen take turns choosing one cell wall and destroying it. For example, two cells $[1, 2], [2, 3]$ become one cell $[1, 3]$ when cell wall $2$ is destroyed. YUKI moves first and Minajigen moves second. Minajigen wants to make the size of the final cell as small as possible, and YUKI wants to make the size of the final cell as large as possible. Find the size of the final cell when both players act optimally.
Input
$N$ $A_1$ $A_2$ $\cdots$ $A_N$
The sequence $A$ defined by $A_i = x_{i+1}-x_i$ is given.
- All inputs are integers
- $1 \leq N \leq 10^5$
- $1 \leq A_i \leq 10^9$
Output
Output the size of the final cell. Print a newline at the end.
Sample
Sample 1
Input
1 10
Output
10
There is only one cell from the beginning.
Sample 2
Input
2 1 10
Output
11
Sample 3
Input
3 1 10 100
Output
11
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
37zigen