問題一覧 > 通常問題

No.2542 Yokan for Two

レベル : / AI推定難易度 : 1475 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 93
作問者 : Shirotsume / テスター : 👑 p-adic 👑 Nachia
お気に入りにしたユーザー ProblemId : 9876 / 自分の提出
問題文最終更新日: 2023-11-15 16:41:49
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 413 (順位表) の他の問題:

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.

  1. Choose an odd number $k$ between $1$ and $N$, inclusive.
  2. Choose $k$ notches out of the $N$ notches, and cut the yokan at the chosen notches.
  3. 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.
  4. A receives all the odd-numbered pieces, and B receives all the even-numbered pieces.
When the yokan is shared by the above procedure, let $A$ be the total length of the pieces A receives, and $B$ be the total length of the pieces B receives. Find the minimum possible value of $|A - B|$.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。