Chip Exchange
골드 IV의견: 0
Bessie the cow has in her possession \(A\) chips of type A and \(B\) chips of type B
(\(0\le A,B\le 10^9\)). She can perform the following operation as many times as
she likes:
- If you have at least \(c_B\) chips of type B, exchange \(c_B\) chips of type B for \(c_A\) chips of type A (\(1\le c_A,c_B\le 10^9\)).
Determine the minimum non-negative integer \(x\) such that the following holds:
after receiving \(x\) additional random chips, it is guaranteed that Bessie can end
up with at least \(f_A\) chips of type A (\(0\le f_A\le 10^9\)).
Problem credits: Benjamin Qi
SCORING
- Input 3: \(c_A=c_B=1\)
- Inputs 4-5: \(x\le 10\) for all cases
- Inputs 6-7: \(c_A=2\), \(c_B=3\)
- Inputs 8-12: No additional constraints.
Problem credits: Benjamin Qi
The first line contains \(T\), the number of independent test cases
(\(1\le T\le 10^4\)).
Then follow \(T\) tests, each consisting of five integers \(A,B,c_A,c_B,f_A\).
Output the answer for each test on a separate line.
Note: The large size of integers involved in this problem may require the use
of 64-bit integer data types (e.g., a "long long" in C/C++).
2
2 3 1 1 6
2 3 1 1 41
05
0 0 2 3 5
0 1 2 3 5
1 0 2 3 5
10 10 2 3 5
0 0 1 1000000000 10000000009
8
7
0
1000000000000000000For the first test, Bessie initially starts with no chips. If she receives any \(9\)
additional chips, she can perform the operation to end up with at least \(5\)
chips of type A. For example, if she receives \(2\) chips of type A and \(7\) chips
of type B, she can perform the operation twice to end up with \(6\ge 5\) chips of
type A. However, if she only receive \(8\) chips of type B, she can only end up
with \(4<5\) chips of type A.
For the fourth test, she already has enough chips of type A from the start.
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > First Contest > Bronze
평가 및 의견
Chip Exchange
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Chip Exchange