레이팅 미적용베시가 베이커리를 열었다!
베시의 베이커리에는 쿠키 하나를 \(t_C\) 단위 시간에, 머핀 하나를 \(t_M\) 단위 시간에 만들 수 있는 오븐이 있다 (\(1\le t_C,t_M\le 10^9\)). 공간이 부족해서 베시는 한 번에 하나의 빵만 만들 수 있으므로, 쿠키 \(A\)개와 머핀 \(B\)개를 만드는 데는 \(A \cdot t_C + B \cdot t_M\) 단위 시간이 걸린다.
베시의 친구 \(N\) (\(1\le N\le 100\))명이 한 명씩 차례로 베이커리를 방문하려고 한다. \(i\)번째 친구는 들어오자마자 쿠키 \(a_i\) (\(1 \leq a_i\leq 10^9\))개와 머핀 \(b_i\) (\(1 \leq b_i \leq 10^9\))개를 주문한다. 베시는 빵을 보관할 공간이 없으므로 주문을 받은 뒤에야 빵을 만들기 시작한다. 게다가 베시의 친구들은 매우 바빠서, \(i\)번째 친구는 \(c_i\) (\(a_i + b_i \leq c_i \leq 2 \cdot 10^{18}\)) 단위 시간까지만 기다리고, 그 이상이면 슬퍼하며 떠난다.
베시는 친구들이 슬퍼하는 것을 정말 원하지 않는다. 1무니로 베시는 오븐을 업그레이드하여 쿠키 하나를 만드는 시간을 1 줄이거나 머핀 하나를 만드는 시간을 1 줄일 수 있다. 오븐을 소수 횟수만큼 업그레이드할 수는 없지만, 쿠키를 만드는 시간과 머핀을 만드는 시간이 모두 양수로 유지되는 한, 친구들이 도착하기 전에 필요한 만큼 여러 번 업그레이드할 수 있다.
\(T\) (\(1 \leq T \leq 100\))개의 테스트 케이스 각각에 대해, 베시의 베이커리가 모든 친구를 만족시킬 수 있도록 베시가 써야 하는 무니의 최소량을 구하도록 도와준다.
출제자: Benjamin Qi
배점
- 입력 2-4: \(N \leq 10, t_C, t_M \leq 1000\)
- 입력 5-11: 추가 제약이 없다.
출제자: Benjamin Qi
첫째 줄에 테스트 케이스의 수 \(T\)가 주어진다.
각 테스트 케이스는 \(N\), \(t_C\), \(t_M\)이 주어지는 한 줄로 시작한다. 그다음 \(N\)개의 줄에 각각 세 정수 \(a_i,b_i, c_i\)가 주어진다.
연속한 테스트 케이스 사이는 빈 줄로 구분된다.
각 테스트 케이스에 대해 베시가 써야 하는 무니의 최소량을 한 줄에 하나씩 출력한다.
2
3 7 9
4 3 18
2 4 19
1 1 6
5 7 3
5 9 45
5 2 31
6 4 28
4 1 8
5 2 2211
6In the first test case, Bessie can pay 11 moonies to decrease the time required
to produce a cookie by 4 and a muffin by 7, so that her oven produces cookies in
3 units of time and muffins in 2 units of time. Then she can satisfy the first
friend in 18 units of time, the second friend in 14 units of time, and the third
friend in 5 units of time, so none of them will get sad and leave.
In the second test case, Bessie should decrease the time required to produce a
cookie by 6 and a muffin by 0.
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > February > Silver