RiseOJ – 칩 교환

설명

소 베시는 A 유형 칩 $$A$$ 개와 B 유형 칩 $$B$$ 개 ( $0\le A,B\le 10^9$ )를 가지고 있다. 베시는 다음 연산을 원하는 만큼 수행할 수 있다.

B 유형 칩을 $$c_B$$ 개 이상 가지고 있다면, B 유형 칩 $$c_B$$ 개를 A 유형 칩 $$c_A$$ 개로 교환한다 ( $1\le c_A,c_B\le 10^9$ ).

다음이 성립하는 최소 음이 아닌 정수 $$x$$ 를 구하라: 추가로 무작위 칩 $$x$$ 개를 받은 뒤, 베시가 A 유형 칩을 최소 $$f_A$$ 개 ( $0\le f_A\le 10^9$ ) 가진 상태로 끝낼 수 있음이 보장된다.

Problem credits: Benjamin Qi

제약

SCORING

입력 3: $$c_A=c_B=1$$
입력 4-5: 모든 케이스에서 $x\le 10$
입력 6-7: $$c_A=2$$ , $$c_B=3$$
입력 8-12: 추가 제약 없음.

Problem credits: Benjamin Qi

입력 형식

첫째 줄에 독립적인 테스트 케이스의 수 $$T$$ ( $1\le T\le 10^4$ )가 주어진다.

이어서 $$T$$ 개의 테스트가 주어지며, 각 테스트는 다섯 정수 $$A,B,c_A,c_B,f_A$$ 로 구성된다.

출력 형식

각 테스트에 대한 답을 한 줄에 하나씩 출력한다.

참고: 이 문제에 등장하는 정수의 크기가 크므로 64비트 정수 자료형(예: C/C++의 "long long")을 사용해야 할 수 있다.

예제 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

설명

For 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

올림피아드 > USACO > 2025-2026 > First Contest > Bronze

태그

JudgeUSACO

칩 교환

평가 및 의견

풀이 제출