Trao Đổi Chip

Lời giải: Trao Đổi Chip

Hướng tiếp cận

Phân tích toán học để giải mỗi test case trong $O(1)$.

Nhận xét quan trọng

1. Kiểm tra $x=0$: đổi tối đa $B$ chip loại B thành A, nếu $A+\lfloor B/c_B\rfloor ·c_A\ge f_A$ thì đáp án là $0$.
2. Khi $x>0$, đối thủ phân phối $x$ chip thành $n_A$ loại A và $n_B$ loại B ($n_A+n_B=x$) để tối thiểu hóa số chip A Bessie đạt được.
3. Bessie đạt được $A+n_A+\lfloor (B+n_B)/c_B\rfloor ·c_A$ chip A.
4. Ta cần tìm $x$ nhỏ nhất sao cho với mọi $(n_A,n_B)$ thỏa $n_A+n_B=x$, biểu thức trên $\ge f_A$.

Độ phức tạp

• Thời gian: $O(T)$
• Bộ nhớ: $O(1)$