컨베이어 벨트 분류
브론즈 I의견: 0
공장의 컨베이어 벨트 위로 상자들이 차례대로 도착한다. \(i\)번째 상자의 무게는 \(w_i\) 이다.
각 상자는 무게에 따라 두 개의 활송 장치(슈트)로 분류된다. 임계 무게 \(T\) 가 주어질 때,
- 무게가 \(T\) 보다 큰 상자는 슈트 A (무거운 상자용) 로 보낸다.
- 무게가 \(T\) 이하인 상자는 슈트 B (가벼운 상자용) 로 보낸다.
각 슈트에는 용량이 있다. 슈트 A의 용량은 \(C_A\), 슈트 B의 용량은 \(C_B\) 이다. 각 슈트는 지금까지 받아들인 상자들의 무게 합(적재량)을 유지한다. 어떤 상자를 한 슈트로 보낼 때, 그 상자를 더했을 때 해당 슈트의 적재량이 용량을 초과하게 된다면, 그 상자는 받아들여지지 않고 벨트 끝에서 떨어져 거부(reject) 된다. 거부된 상자는 어느 슈트의 적재량도 늘리지 않는다. 그렇지 않으면 상자는 받아들여지고 그 무게가 해당 슈트의 적재량에 더해진다.
상자들을 도착 순서대로 처리할 때, 각 상자의 행선지를 차례대로 출력하라. 행선지는 슈트 A로 가면 A, 슈트 B로 가면 B, 거부되면 R 이다. 또한 모든 처리가 끝난 뒤 각 슈트의 최종 적재량을 출력하라.
\(1 \le N \le 200{,}000\)
\(0 \le T \le 10^9\)
\(0 \le C_A, C_B \le 10^{18}\)
\(1 \le w_i \le 10^9\)
첫째 줄에 네 정수 \(N\), \(T\), \(C_A\), \(C_B\) 가 공백으로 구분되어 주어진다. \(N\)은 상자의 개수, \(T\)는 임계 무게, \(C_A\)와 \(C_B\)는 각 슈트의 용량이다.
둘째 줄에 \(N\)개의 정수 \(w_1, w_2, \dots, w_N\) 이 공백으로 구분되어 주어진다. \(w_i\)는 \(i\)번째로 도착하는 상자의 무게이다.
첫째 줄에 각 상자의 행선지를 도착 순서대로 공백으로 구분하여 출력한다. (\(i\)번째 상자가 슈트 A면 A, 슈트 B면 B, 거부되면 R)
둘째 줄에 슈트 A의 최종 적재량과 슈트 B의 최종 적재량을 공백으로 구분하여 출력한다.
6 5 20 15
8 3 10 7 2 5
A B A R B B
18 10
임계값 \(T=5\), A 용량 20, B 용량 15.
8 > 5 → A (적재 8 ≤ 20) → A
3 ≤ 5 → B (적재 3 ≤ 15) → B
10 > 5 → A (적재 18 ≤ 20) → A
7 > 5 → A (18+7=25 > 20) → 거부 R
2 ≤ 5 → B (적재 5 ≤ 15) → B
5 ≤ 5 → B (적재 10 ≤ 15) → B
최종 A 적재 = 18, B 적재 = 10
1 3 0 0
10
R
0 0
10 > 3 이므로 A로 보내려 하지만 A 용량이 0이라 적재할 수 없어 거부된다. 두 슈트 모두 적재량 0.
riseoj 작성
출처 Original
평가 및 의견
컨베이어 벨트 분류
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
컨베이어 벨트 분류