IOI 2005 day1 3- 경사 조절(Mountain) > 문제은행 : 정보올림피아드&알고리즘




1149 : 경사 조절(Mountain)

제한시간
3000 ms   
메모리제한
256 MB   
해결횟수
3 회   
시도횟수
33 회   

문제

동현이가 경영하는 산악 유원지에서는 레일의 경사를 마음대로 조절할 수 있는 획기적인 스타일의 롤러 코스터를 선보였다. 

롤러 코스터가 다니는 선로는 n개의 레일로 이루어져 있으며, 각 레일의 끝은 다음 레일의 시작과 연결된 형태이다. 

첫 레일의 시작은 고도가 항상 0이나, 각 레일의 끝부분은 롤러 코스터 운영자인 동현이는 높이를 얼마든지 조절할 수 있다. 

레일의 시작과 끝의 높이가 다르면 롤러 코스터가 다니는 길에 경사가 생기는 것이다.

 

경사 조절은 이어져 있는 여러 레일을 상대로 일괄적으로 할 수 있다. 

이 경우, 높이가 바뀐 레일의 바로 다음 레일들은 시작 부분이 이전 레일의 끝과 연결된 상태를 유지하게끔, 

자신의 기울기(경사)는 유지한 채로 고도만 그대로 하강하거나 상승한다.

 

한편, 이 트랙을 다니는 열차는 고도가 0인 초기 위치에서 고도가 h인 지점까지 오를 수 있는 추진력을 한 번만 받은 후, 

그 뒤부터는 그 높이에 다다르거나 레일을 모두 지날 때까지 관성으로 다닌다. 물론 레일에는 마찰이 없다고 가정한다.

 

초기에는 모든 레일들이 고도가 0인 위치에서 수평을 이루고 있다. 

그러나 동현이는 각 레일의 고도도 마음대로 조정하고, 그 상태에서 열차 운행도 초기 추진력을 무작위로 줘 가며 한다. 

해당 상태에서 열차를 h까지 갈 수 있는 힘을 받아서 출발했을 때, 열차가 어느 레일까지 갈 수 있는지를 계산하는 프로그램을 작성하시오.

 

 


입력형식

첫 줄에는 레일의 개수 n이 있다. (1 <= n <= 10억) 그리고 다음부터는 순차적으로 레일의 경사를 재조정하거나 그 상태에서 열차를 운행한 기록이 한 줄에 하나씩 들어있으며, 마지막으로 입력의 끝임을 나타내는 표시로 입력이 끝난다. 즉, 각 줄에는 다음 중 한 가지 형태의 정보가 있다. • 경사 조정 : 알파벳 'I', 그리고 정수 a, b, D (1 <= a <= b <= n, -10억 <= D <= 10억). a번 레일의 시작 부분의 고도를 기준점으로 하여 b번 레일의 끝구간까지를, 경사가 D인 일직선이 되게 한다. b번 이후의 레일들은 b번 레일 끝 부분의 고도에 맞춰 높이가 평행이동된다. • 열차 운행 : 알파벳 'Q', 그리고 열차가 받은 추진력으로 올라갈 수 있는 최대 높이 h (0 <= h <=10억) • 입력의 끝임을 나타내는 알파벳 'E' 경사를 조정하는 과정에서 레일 한쪽 끝의 고도 역시 0에서 10억 사이임이 보장된다. 또한 입력량은 10만 줄을 넘지 않는다. 테스트 케이스들의 절반은 1 <= n <= 20,000이며, 입력량 역시 1,000줄 이내이다.

출력형식

명령이 들어왔을 때 레일 상태의 변화를 잘 파악하고 있다가, Q 명령이 들어오면 그만한 힘을 받은 열차가 몇째 레일까지 완주할 수 있는지 계산하여 그 레일 번호를 출력하면 된다.

입력 예

4
Q 1
I 1 4 2
Q 3
Q 1
I 2 2 -1
Q 3
E

출력 예

4
1
0
3

Hint!

아래 그림의 x축이 레일 번호를, y축은 고도를 뜻한다. 정점 위에 있는 수는 해당 레일의 시작/끝점의 고도이며, 선분 위에 있는 수는 그 레일의 경사이다. 초기에는 모든 레일이 경사가 없으므로 열차가 마지막 4 번 레일까지 무난히 달릴 수 있다. 그러다가 1번부터 4번까지 2씩 경사가 생긴 뒤에는, 3 이라는 고도까지 올라가는 힘으로는 2번 레일도 완주하지 못한다(끝의 고도가 4임). 그래서 둘째 출력값은 1이다. 하물며 1이라는 힘으로는 아무 레일도 갈 수 없기 때문에 셋째 출력값은 0 이다. 끝으로 2 번 레일의 경사를 2에서 -1로 설정하고 나면 3 번과 4 번 레일의 고도도 -3씩 감소하게 되고, 3 이라는 힘으로 3 번 레일까지는 갈 수 있게 되는 것이다.



경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP