問題一覧 > 通常問題

No.2486 Don't come next to me

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 94
作問者 : takumaiq / テスター : ytqm3 highlighter
4 ProblemId : 10169 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-09-29 22:50:08

問題文

NN 個の席が横一列に並んでいます。
それぞれの席には左から 1,2,...,N1,2, ... ,N と番号が振られています。今、MM 人の人がそれぞれ A1,A2,...,AMA_1, A_2 ,..., A_M に座っています。
これから N−MN-M 人の人が 1 人ずつ部屋に入ってきます。このとき、それぞれの人はそのときの 最も近い人との距離が最大となるような席のうち 1 つ選んで座ります。
最後に座る人が座る席としてありえるものの個数を求めてください。

入力

NN MM
A1A_1 A2A_2 …\ldots AMA_M
  • 1≤N≤10181 \leq N \leq 10^{18}
  • 2≤M≤2×1052 \leq M \leq 2\times 10^5
  • M<NM< N(21:23 訂正)
  • A1=1,AM=NA_1=1,A_M=N
  • Ai<Ai+1A_i < A_{i+1}
  • 入力はすべて整数

出力

最後に改行してください。

サンプル

サンプル1
入力
7 3
1 5 7
出力
3

N−M=7−3=4N-M=7-3=4 人の座る順序として次のようなものが挙げられます。
11 人目は 33 番目の席に座る。
22 人目は 66 番目の席に座る。
33 人目は 22 番目の席に座る。
44 人目は 44 番目の席に座る。
このように、44 番目の席は最後に座る人が座る可能性があります。
同様に、2,62,6番目の席も条件を満たします。
よって 出力すべき値は 33 です。

サンプル2
入力
12 5
1 4 5 7 12
出力
7

空いている席の番号は 2,3,6,8,9,10,112,3,6,8,9,10,11 番ですが、これらの席は全て条件を満たします。

サンプル3
入力
75 18
1 2 8 15 18 19 22 23 25 27 33 38 53 58 60 64 73 75
出力
54

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。