問題
John, Bessie 두 사람이 게임을 하고 있다.
N 개의 돌들이 수직선 위에 놓여 있다.
두 사람은 번갈아가며, 현재 놓인 돌들 중 하나를 선택하여 제거한다.
남아있는 돌이 2개가 되면 게임은 끝난다.
이 2개의 돌 사이의 거리를 D 라고 하자.
John 은 D 를 최대한 크게, Bessie 는 D 를 최대한 작게 만들고 싶어 한다.
초기 돌들의 좌표와, John 과 Bessie 중 누가 먼저 게임을 시작하는 지가 입력된다.
두 사람이 각자의 목표를 위해 최선을 다하여 게임을 진행했을 때, D 를 구하자.
入力
첫 줄에 돌의 개수 N 과, 먼저 시작하는 사람의 이름이 입력된다. ( 3 ≤ N ≤ 105 )
두 번째 줄에 돌들의 좌표
돌들의 좌표는 모두 다르고, 오름차순으로 입력된다.
出力
게임이 끝난 후 D 를 출력한다.
部分問題
| 番号 | 点数 | 条件 |
|---|---|---|
| #1 | 30点 | 돌들의 좌표가 등차수열로 주어진다. |
| #2 | 10点 | 3 ≤ N ≤ 10 |
| #3 | 60点 | 제약 조건 없음 |
例題 #1
5 John
4 5 6 7 8
3
D = 3 이 되는 경우들 중 하나를 적으면 아래와 같다.
John : 6 제거
Bessie : 8 제거
John : 5 제거
例題 #2
5 Bessie
4 5 6 7 8
1
D = 1 이 되는 경우들 중 하나를 적으면 아래와 같다.
Bessie : 8 제거
John : 5 제거
Bessie : 4 제거
出典
Asia Regional Contest 2015 in Tsukuba
ログインしないとコードを書けません。