레이팅 미적용전염성이 매우 강한 소 질병 COWVID-19가 발생한 후, 농부 존은 소들의 건강을 걱정하고 있다.
병의 전파를 막기 위해, 농부 존의 소 \(N\)마리(\(2 \leq N \leq 10^5\))는 "사회적 거리두기"를 실천하며 농장 전체에 흩어져 있기로 했다. 농장은 1차원 수직선 모양이며, 풀을 뜯을 수 있는 서로 겹치지 않는 구간이 \(M\)개(\(1 \leq M \leq 10^5\)) 있다. 소들은 각각 풀이 있는 서로 다른 정수 지점에 자리를 잡아, 가장 가까운 소 쌍 사이의 거리인 \(D\)의 값을 최대화하고 싶다. 소들이 가능한 \(D\)의 최댓값을 구하도록 도와주자.
문제 제공: Brian Dean
배점
- 테스트 케이스 2-3은 \(b\le 10^5\)을 만족한다.
- 테스트 케이스 4-10은 추가 제약이 없다.
문제 제공: Brian Dean
입력의 첫째 줄에 \(N\)과 \(M\)이 주어진다. 다음 \(M\)개의 줄 각각에 구간 하나를 나타내는 두 정수 \(a\)와 \(b\)가 주어진다. 여기서 \(0 \leq a \leq b \leq 10^{18}\)이다. 어떤 두 구간도 겹치거나 끝점에서 맞닿지 않는다. 구간의 끝점에 서 있는 소도 풀 위에 서 있는 것으로 친다.
모든 소 쌍이 서로 \(D\) 단위 이상 떨어져 있도록 할 수 있는 \(D\)의 최댓값을 출력한다. \(D>0\)인 해가 존재함이 보장된다.
socdist.in · 출력을 쓸 파일 socdist.out5 3
0 2
4 7
9 92One way to achieve \(D=2\) is to have cows at positions \(0\), \(2\), \(4\), \(6\) and
\(9\).
riseoj 작성
출처 올림피아드 > USACO > 2019-2020 > US Open > Silver