5회 문제풀이 06 / ABC 214 C - Distribution
ABC 214 C - Distribution
【문제 개요】
N명의 스누케군이 원형으로 앉아있습니다. 사람들은 시계방향으로 1번부터 N번까지 번호가 매겨져 있습니다.
i(1 ≤ i ≤ N)번째의 스누케군은 시각 t에 보석을 받으면 Sᵢ단위시간후, 즉 t + Sᵢ에 그 보석을 (i + 1)번째의 스누케군에게 넘깁니다. 단, (N + 1)번째의 스누케군은 1번째의 스누케군을 의미합니다.
또, 타카하시군은 시각 Tᵢ에 i번째의 스누케군에게 보석을 넘깁니다.
전체의 i(1 ≤ i ≤ N)에 대해서, i번째의 스누케군이 처음으로 보석을 받는 시간을 구하시오. 또, 보석을 주고받는데 소요되는 시간은 무시합니다.
힌트 : 동적 프로그래밍 (Dynamic Programming)
그리디 알고리즘 (Greedy Algorithm)
큐 (Queue)
순환 구조 처리
【전제】
- 입력은 모두 정수이다.
- 1 ≤ N ≤ 200000
- 1 ≤ Sᵢ, Tᵢ ≤ 10⁹
【입력 형태】
1
2
3
N
S₁ S₂ ... Sₙ
T₁ T₂ ... Tₙ
【출력 형태】
N행으로 i번째 줄의 사람이 처음으로 보석을 받는 시간을 출력하시오.
【예시】
입력 예 1
1
2
3
3
4 1 5
3 10 100
출력 예 1
1
2
3
3
7
8
시간 3 : 타카하시군이 1번째의 스누케군에게 보석을 넘깁니다. 시간 7 : 1번째의 스누케군이 2번째의 스누케군에게 보석을 넘깁니다. 시간 8 : 2번째의 스누케군이 3번째의 스누케군에게 보석을 넘깁니다. 시간 10 : 타카하시군이 2번째의 스누케군에게 보석을 넘깁니다. 시간 11 : 2번째의 스누케군이 3번째의 스누케군에게 보석을 넘깁니다. 시간 13 : 3번째의 스누케군이 1번째의 스누케군에게 보석을 넘깁니다. 시간 14 이후에도 각각 스누케군은 보석을 주고받겠지만 답변에 영향은 없습니다.
입력 예 2
1
2
3
4
100 100 100 100
1 1 1 1
출력 예 2
1
2
3
4
1
1
1
1
입력 예 3
1
2
3
4
1 2 3 4
1 2 4 7
출력 예 3
1
2
3
4
1
2
4
7
한 스누케군이 동시에 복수의 보석을 받고 넘기는 가능성이 있다는것, 특히 타카하시군과 옆자리의 스누케군에게 동시에 보석을 받을 가능성이 있다는것에 주의하세요.
입력 예 4
1
2
3
8
84 87 78 16 94 36 87 93
50 22 63 28 91 60 64 27
출력 예 4
1
2
3
4
5
6
7
8
50
22
63
28
44
60
64
27