Trao Đổi Chip

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie có $A$ chip loại A và $B$ chip loại B. Cô có thể đổi $c_{B}$ chip loại B lấy $c_{A}$ chip loại A, thực hiện nhiều lần tùy ý.

Bessie muốn có ít nhất $f_{A}$ chip loại A. Để đạt được điều này, cô nhận thêm $x$ chip ngẫu nhiên (mỗi chip có thể là loại A hoặc B, do đối thủ chọn theo cách bất lợi nhất). Tìm giá trị nhỏ nhất của $x$ (không âm) sao cho bất kể $x$ chip thêm được phân phối thế nào, Bessie luôn đảm bảo đạt được ít nhất $f_{A}$ chip loại A (sau khi đổi tối ưu).

Dữ liệu vào

Dòng 1: Số nguyên $T$ — số test case
$T$ dòng tiếp theo, mỗi dòng chứa 5 số nguyên: $A$ , $B$ , $c_{A}$ , $c_{B}$ , $f_{A}$

Dữ liệu ra

Với mỗi test case, in ra một số nguyên — giá trị nhỏ nhất của $x$ .

Ràng buộc

$1 \leq T \leq 10^{4}$
$0 \leq A, B \leq 10^{9}$
$1 \leq c_{A}, c_{B} \leq 10^{9}$
$0 \leq f_{A} \leq 10^{9}$
Sử dụng kiểu dữ liệu 64-bit

Ví dụ

Input	Output	Giải thích
2 2 3 1 1 6 2 3 1 1 4	1 0	Test 1: Bessie có 2A+3B, đổi 3B thành 3A, được 5A. Cần thêm 1 chip. Test 2: đã đủ 5A $\geq$ 4.
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	Xem giải thích chi tiết trong lời giải.

Bình luận

Không có bình luận tại thời điểm này.