문제
올정마을의 중심 도로에는 n개의 버스 정류장이 있다. 도로는 하나의 직선처럼 생겼으며, 가장 왼쪽에 있는 버스 정류장을 0이라 했을 때, 각 버스 정류장의 위치는 가장 왼쪽 정류장으로부터의 거리로 나타낼 수 있다. 예를 들어 버스 정류장 위치 0, 10, 40, 100은 다음과 같다.
버스 경로는 0에서 맨 오른쪽까지 가는 경로 하나뿐이다. 버스는 매 w분마다 맨 좌측 정류장에서 출발하여, 맨 우측까지, 오른쪽으로만 v의 속도로 달려간다. 첫 버스의 출발시간은 0분이다. 버스는 매 정류장마다 멈춰서 사람들을 태운다. 사람들을 태우는데는 시간이 들지 않는다.
q명의 주민들이 올정마을 맨 오른쪽 정류장에 있는 바자회에 가려고 한다. 1번부터 q번까지의 주민이 있다고 할 때, i번 주민은 p[i]에서 t[i]분에 출발하여, u[i]의 속도로 걸을 수 있다. 주민은 한번 t[i]분에 출발하면, 좌우 어디로든 걸어갈 수 있으며, 버스 정류장에서 걷지 않고 버스를 기다릴수도 있다. 버스가 버스 정류장에 있을 때, 주민 i가 버스 정류장에 있으면, 주민은 버스를 탈 수 있다.
각 q명의 주민들이 가장 오른쪽 정류장에 도착하는 최소 시간을 출력하는 프로그램을 작성하라. 총 이동 시간을 구하는 것이 아닌, 처음 0분부터 도착할 때까지 걸린 시간을 출력한다.
입력
표준 입력으로 다음 정보가 주어진다. 첫 줄에 정수 n이 주어진다. n은 버스 정류장의 수이다. (2 <= n <= 150,000 , n은 정수)
다음 줄에 n개의 버스 정류장의 위치 x[1], x[2], … x[n]이 각각 주어진다. (x[1] = 0 < x[2] < x[3] < … < x[n] <= 109)
셋째 줄에 버스의 주기와 속도인 w와 v가 주어진다.(1 <= w, v <= 109)
넷째 줄에 주민 수인 q가 주어진다.(1 <= q <= 150,000) 다음 q줄 다음이 주어진다.
i+4번째 줄에 각 i번 주민을 묘사하는 p[i], t[i] 그리고 u[i]가 주어진다. (0 < p[i] < x[n]) (0 <= t[i]<= 109 , 1 <= u[i] <= 109)
출력
표준 출력으로 총 q줄을 출력한다.
i번째 줄에, i번 주민이 맨 오른쪽 버스 정류장에 도착하는 최소 시간을 출력한다.
시간은 몇분 몇초의 형식이 아닌, 소수점 형태로 출력한다.
정답과 10-5이하로 차이 나는 출력은 정답으로 인정한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 5점 | 올정마을 주민들은 다리근육이 발달해서 모두 버스보다 속도가 빠르다. |
| #2 | 10점 | n = 2 |
| #3 | 25점 | 2 <= n <= 3,000, 1 <= q <= 3,000 |
| #4 | 60점 | 원래의 제약조건 이외에 아무 제약조건이 없다. |
예제
4
0 10 40 100
20 10
3
0 0 4
15 10 1
40 2 16
10.0000000000
30.0000000000
5.7500000000
로그인해야 코드를 작성할 수 있어요.