BOJ 7962 A Journey to Mars

문제 링크:

문제 내용

원형으로 이루어진 도로 위의 $n$개의 지점에 주유소가 있습니다. 각 주유소의 위치와 그 주유소에서 차에 넣을 수 있는 연료의 양이 주어질 때, 각 주유소에서 시작하여 두 방향 중 한 방향으로 도로를 한 바퀴 돌아서 제자리로 돌아올 수 있는지 판별하세요.

맨 처음에 차의 연료통은 비어 있으며, 시작점에서 주유를 한 뒤 이동을 시작합니다. 1만큼의 연료가 있으면 1만큼의 거리를 이동할 수 있습니다. 차의 연료통에는 연료 제한이 없습니다.

입력

첫 줄에는 주유소의 개수 $n$이 주어집니다. ($3 \le n \le 1\;000\;000$)

다음 $n$줄에 걸쳐서, $i$번째 줄에는 먼저 $i$번째 주유소에서 넣을 수 있는 연료의 양이 주어지고, 그 다음에 $i$번째 주유소에서 $i+1$번째 주유소까지의 거리가 주어집니다. (마지막 거리는 $n$번째 주유소에서 첫 번째 주유소까지의 거리를 나타냅니다.) 연료의 양은 음이 아닌 정수, 거리는 양의 정수이며, 연료의 합과 거리의 합은 각각 $2\;000\;000\;000$을 초과하지 않습니다.

출력

$n$줄에 걸쳐서, $i$번째 주유소에서 시작하여 한 바퀴를 돌 수 있으면 $i$번째 줄에 TAK을, 아니라면 NIE를 출력합니다.

문제 풀이