No.2542 Yokan for Two
タグ : / 解いたユーザー数 93
作問者 :
Nachia
Problem Statement
There is a yokan whose length in the left-right direction is $L$. The yokan has $N$ notches, and the $i$-th notch from the left is located at a distance of $X_i$ from the left end of the yokan.
A and B are going to share this yokan by the following procedure.
- Choose an odd number $k$ between $1$ and $N$, inclusive.
- Choose $k$ notches out of the $N$ notches, and cut the yokan at the chosen notches.
- The yokan is divided into $k + 1$ pieces (which is an even number). Number the resulting pieces $1, 2, \dots, k + 1$ from left to right.
- A receives all the odd-numbered pieces, and B receives all the even-numbered pieces.
Constraints
- All input values are integers.
- $2 \leq L \leq 10^5$
- $1 \leq N \leq 100$
- $0 \lt X_1 \lt \dots \lt X_N \lt L$
Input
The input is given from standard input in the following format.
$L$ $N$ $X_1$ $X_2$ $\dots$ $X_N$
Output
Find the minimum possible value of $|A - B|$.
Sample
Sample 1
Input
5 2 1 3
Output
1
A yokan of length $5$ has notches at positions $1, 3$ from the left. If the yokan is cut at the $2$nd notch, it is divided into pieces of lengths $3, 2$.
In this case, A receives piece $1$ of length $3$ and B receives piece $2$ of length $2$, so $|A - B| = 1$. It is impossible to make $|A - B|$ smaller than this, so the answer is $1$.
Sample 2
Input
9 3 1 2 7
Output
3
A yokan of length $9$ has notches at positions $1, 2, 7$ from the left. If the yokan is cut at all the notches, it is divided into $4$ pieces of lengths $1, 1, 5, 2$.
A takes pieces $1, 3$ and B takes pieces $2, 4$. Therefore, $|A - B| = |6 - 3| = 3$. It is impossible to make $|A - B|$ any smaller, so the answer is $3$.
Sample 3
Input
2 1 1
Output
0
Sample 4
Input
100000 30 3094 4822 5682 6189 6494 6505 8276 8758 9856 11633 14312 16150 16304 20183 22646 23645 24327 25607 26464 32214 32407 33177 39608 41552 42802 44344 44706 45451 49184 97259
Output
1632
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。