No.2486 Don't come next to me
タグ : / 解いたユーザー数 92
作問者 :
takumaiq
/ テスター :
ytqm3
highlighter
Problem Statement
$N$ seats are arranged in a horizontal row.
The seats are numbered $1,2, ... ,N$ from the left. Currently, $M$ people are sitting at $A_1, A_2 ,..., A_M$ respectively.
From now on, $N-M$ people will enter the room one at a time. Each person chooses and sits in one of the seats that maximize the distance to the nearest person at that time.
Find the number of seats in which the last person to sit could possibly sit.
Input
$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_M$
- $1 \leq N \leq 10^{18}$
- $2 \leq M \leq 2\times 10^5$
- $M< N$ (corrected at 21:23)
- $A_1=1,A_M=N$
- $A_i < A_{i+1}$
- All inputs are integers
Output
Print a newline at the end.
Sample
Sample 1
Input
7 3 1 5 7
Output
3
One possible seating order of the $N-M=7-3=4$ people is as follows.
The $1$st person sits in seat $3$.
The $2$nd person sits in seat $6$.
The $3$rd person sits in seat $2$.
The $4$th person sits in seat $4$.
Thus, seat $4$ may be taken by the last person to sit.
Similarly, seats $2,6$ also satisfy the condition.
Therefore, the value to output is $3$.
Sample 2
Input
12 5 1 4 5 7 12
Output
7
The empty seats are $2,3,6,8,9,10,11$, and all of these seats satisfy the condition.
Sample 3
Input
75 18 1 2 8 15 18 19 22 23 25 27 33 38 53 58 60 64 73 75
Output
54
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。