[BOJ/백준] 30640 - 운전 연습

30640번: 운전 연습

---

해당 위치까지 갈 수 있다는 것은 마법사를 만나도 0번째 위치로 이동해서 다시 올 수 있다

 

해당 위치까지 갈 수 없다는 것은 마법사를 만나도 다시 올 수 없다

 

순간이동을 해서 다시 올 수 있음은 다음 조건으로 확인할 수 있다

 

순간이동한 곳까지 Cost = A

마법사를 만난 곳까지 Cost = B

 

A <= B 가능

A > B 일 경우 A - B < B 이어야만 가능

---

---

• 제목

운전 연습

---

• 조건

시간 제한 : 1 초

메모리 제한 : 1024 MB 

---

• 문제

장롱 면허를 보유한 시은이는 수직선 위에서 운전 연습을 하려고 한다. 시은이는 원점에서 출발하여 항상 양의 방향으로 이동할 것이다. 자동차는 단위 거리 1만큼 이동하는데 전기 1kWh를 소모하며, 전기를 소모하는 방법은 이동하기 밖에 없다. 처음 상태의 자동차는 전기가 없으며, 전기가 없는 자동차는 충전하기 전엔 이동할 수 없다.

수직선 위에는 0번부터 N번까지, 총 N + 1개의 충전소가 있다. i번 충전소는 수직선 위의 점 Ai에 있으며 방문하면 Fi kWh의 전기를 충전할 수 있다. 0번 충전소를 제외한 나머지 충전소들 중 하나에는 장난꾸러기 마법사가 숨어있다. 마법사는 시은이가 해당 충전소에 도착하면 그보다 이전에 있는(즉, 원점에 더 가까운) 충전소들 중 하나로 순간이동하게 만든다. 재미있게도 순간이동할 충전소는 시은이가 고를 수 있다. 순간이동에 의해 소비되는 전기는 없으며, 마법사는 한 번 장난을 치면 다시는 장난을 치지 않는다.

마법사가 장난을 칠 때에는 충전을 할 수 없으며, 순간이동을 통해 다시 만난 충전소에서는 충전을 할 수 있다. 예를 들어 시은이가 3번 충전소에서 마법사를 만나 1번 충전소로 순간이동 하기로 했다면, 0 → 1 → 2 → (마법사의 장난에 의해 3번에서 충전을 하지 못함) → 1 → 2 → 3 → … 번 충전소의 순서로 자동차를 충전할 수 있다.

시은이가 각 충전소에서 마법사를 만났다고 가정했을 때, 원점으로부터 가장 먼 위치에서 자동차가 방전되게 하려면 몇 번 충전소를 선택해야 할지 알아보자.

---

• 입력

첫째 줄에 0번 충전소를 제외한 충전소의 수 N이 주어진다.

다음 N + 1개의 줄에 걸쳐, 각 줄에 0번 충전소부터 번호의 오름차순으로 i번 충전소의 정보 Ai와 Fi가 공백으로 구분되어 주어진다.

---

• 출력

총 N줄을 출력해야 하며, i번째 줄에는 두 정수 xi와 yi를 공백으로 구분하여 출력한다. (1 ≤ i ≤ N)

마법사를 만나지 않은 채로 i번 충전소에 도달할 수 없다면

• xi와 yi는 모두 -1이다.

그 밖의 경우

• xi는 i번 충전소에서 마법사를 만났을 때 시은이가 선택해야 할 충전소의 번호이다.
• yi는 xi번 충전소로 순간이동 한 뒤 다시 i번 충전소로 돌아왔을 때, 자동차에 충전된 전기의 변화량이다.
• 단, 조건을 만족하는 xi가 여러가지라면 가장 큰 것을 출력한다.

---

• 제한

1 ≤ N ≤ 200,000
A0 = 0
A0 < A1 < A2 < ... < AN ≤ 1012
1 ≤ Fi ≤ 106 (0 ≤ i ≤ N)
자동차에는 무한히 많은 전기를 충전할 수 있다.
입력으로 주어지는 수는 모두 정수다.

---

예제 입력1	예제 출력1
3 0 2 2 5 6 8 100 1	0 0 1 1 -1 -1

 

예제 입력2	예제 출력2
5 0 5 3 1 6 5 10 2 13 8 15 2	0 2 0 0 2 1 2 0 4 6

---

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        long[] loc = new long[N + 1];
        long[] sum = new long[N + 1];
        long[] able = new long[N + 1];
        for (int i = 0; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            long l = Long.parseLong(st.nextToken());
            long e = Long.parseLong(st.nextToken());
            loc[i] = l; sum[i] = e;
            if(i != 0) sum[i] += sum[i - 1];
            if(i != 0) able[i] = sum[i - 1] - loc[i];
        }
        boolean impossible = false;
        int index = 0;
        for (int i = 1; i <= N; i++) {
            if(able[i] < 0) impossible = true;
            if(impossible){
                sb.append(-1).append(" ").append(-1).append('\n');
            } else {
                sb.append(index).append(" ").append(able[i]).append('\n');
            }
            if(able[i] == 0) index = i;
        }
        System.out.println(sb);
    }
}