| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 680 | 271 | 215 | 41.992% |
성현이는 바나나 푸딩을 만들기 위해 먼저 버터를 녹이려고 한다. 이를 위해 양쪽으로 무한히 뻗은 직선 모양의 프라이팬에 각각 홀수 높이의 버터 $N$개를 올려놓고, 열을 가해서 버터를 녹인다. 위치가 $x$인 곳에 올려진 버터는 처음에 구간 $[x,x]$를 차지하고, 열을 가하면 처음 버터가 올려진 부분의 높이가 1이 될 때까지 1초에 좌우로 1씩 퍼지게 된다. 즉, $[L,R]$이었던 버터는 1초 후 $[L-1,R+1]$를 차지하게 된다. 다음 예시는 위치 $x=5,ドル 높이 $h=7$인 버터가 녹는 과정이다.
이때 서로 다른 두 버터가 녹아서 섞이게 될 수 있다. 두 버터가 섞인다는 것은, 두 버터가 각각 $[l_1,r_1]$와 $[l_2,r_2]$에 놓였을 때 겹치는 구간이 생기는 것을 의미한다. 즉, $[l_1,r_1] \cap [l_2,r_2] \neq \emptyset$ 인 경우이다. 다음은 예제 1번의 상황을 그림으로 나타낸 것이다.
2초의 상황으로 두 버터가 섞이지 않는다.
3초까지 가열하면 $x=2$에서 섞이게 된다.
성현이는 어떤 두 버터도 섞이지 않을 때까지만 버터를 녹이고 싶다. 그러나 성현이는 정수 시간만큼만 가열할 수 있다. 즉, 3초나 4초를 가열할 수는 있지만, 3.5초나 3.105초를 가열할 수는 없다. 직선 모양의 프라이팬에 처음 버터를 놓은 위치 $x$와 버터의 높이 $h$가 $N$개 주어졌을 때, 성현이가 얼마나 오랜 시간 버터를 가열할 수 있는지 알아보자.
입력은 다음과 같이 주어진다.
$N$
$x_1$ $h_1$
$x_2$ $h_2$
$\cdots$
$x_{N-1}$ $h_{N-1}$
$x_N$ $h_N$
첫째 줄에 성현이가 올린 버터의 수 $N$이 주어진다.
이어 $N$개의 줄에 걸쳐 버터가 놓인 좌표 $x_i$와 버터의 높이 $h_i$가 공백으로 구분되어 주어진다.
성현이가 얼마나 오랜 시간 버터를 가열할 수 있는지 출력한다. 만약 성현이가 10ドル^{100}$초 이상 가열할 수 있다면, forever를 출력한다.
2 1 3 5 7
2
2초간 가열하면 녹은 버터는 각각 $[0,2],ドル $[3,7]$에 위치한다. 3초를 가열하면 섞이기 때문에 2초까지만 가열할 수 있다.
2 5 5 1 5
1
1초간 가열하면 녹은 버터는 각각 $[0,2],ドル $[4,6]$에 위치한다. 2초를 가열하면 섞이기 때문에 1초까지만 가열할 수 있다.
3 -1 1 19191919 7 100 3
forever
성현이가 10ドル^{100}$초 이상 가열해도 어떠한 버터도 섞이지 않는다.
University > 연세대학교 > 2023 연세대학교 프로그래밍 경진대회 B번