頁面無法載入？點擊這裡可能會修復。
Placeholder

#8840
子任務

칩 교환 1s 1024MB

問題

베시라는 소는 A형 칩을 A개, B형 칩을 B개 가지고 있다(0 ≤ A, B ≤ 10^9).

베시는 다음 연산을 원하는 만큼 여러 번 수행할 수 있다.

  • B형 칩이 c_B개 이상 있다면, B형 칩 c_B개를 A형 칩 c_A개로 교환한다(1 ≤ c_A, c_B ≤ 10^9).

다음 조건을 만족하게 만드는 최소의 음이 아닌 정수 x를 구하라:

x개의 임의의(무작위) 칩을 추가로 받은 뒤에는, 그 칩들이 A형과 B형으로 어떻게 섞여 들어오든 간에,

베시가 결국 A형 칩을 f_A개 이상(0 ≤ f_A ≤ 10^9) 가지게 되는 것이 보장되어야 한다.


輸入

첫 줄에 서로 독립적인 테스트 케이스의 수 T가 주어진다(1 ≤ T ≤ 10^4).

이후 T개의 테스트가 이어지며, 각 테스트는 다섯 정수 A, B, c_A, c_B, f_A로 이루어진다.


輸出

각 테스트 케이스마다 정답을 한 줄에 하나씩 출력하라.

참고: 이 문제에서 다루는 정수의 크기가 매우 크므로, 64비트 정수형(예: C/C++의 long long)이 필요할 수 있다.


子任務

編號 分數 條件
#110分

c_A = c_B = 1

#220分

x \le 10

#330分

c_A =2, c_B = 3

#440分

추가 제약 조건 없음


範例 #1

2
2 3 1 1 6
2 3 1 1 4
1
0

範例 #2

5
0 0 2 3 5
0 1 2 3 5
1 0 2 3 5
10 10 2 3 5
0 0 1 1000000000 1000000000
9
8
7
0
1000000000000000000

첫 번째 테스트 케이스에서, 베시는 처음에는 칩이 하나도 없다. 만약 추가로 어떤 형태로든 9개의 칩을 받기만 하면, 베시는 연산을 적절히 수행하여 A형 칩을 최소 5개 이상 만들 수 있다. 예를 들어 A형 2개와 B형 7개를 받으면, 연산을 2번 수행하여 A형 칩을 6개로 만들 수 있으므로 6 ≥ 5를 만족한다. 하지만 만약 B형 칩 8개만 받는다면, 연산을 통해 얻는 A형 칩이 4개에 불과하여 4 < 5가 된다.

네 번째 테스트 케이스에서는, 시작부터 이미 A형 칩을 충분히 가지고 있다.



來源

USACO 2026 First Contest, Bronze
需要登入才能撰寫程式碼。