Editorial for Bedao Regular Contest 04 - MARBLE


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Sử dụng tìm kiếm nhị phân. Nếu chọn ~X~ người cho ra kết quả hợp lệ thì khi chọn ~Y < X~ người cũng chắc chắn hợp lệ.

Nếu ~a = b~ thì kết quả là ~min(x~, ~y)~ / ~a~;

Nếu ~a~ > ~b~ (nếu không thì swap lại), ta có các bất đẳng thức sau:

  • ~x \leq a \times k + b \times (n - k)~

  • ~y \leq a \times (n - k) + b \times k~

Biến đổi đưa thành ~1~ biến ~k~ duy nhất:

  • ~(x - b \times n) / (a - b) \leq k~

  • ~(y - a \times n) / (b - a) \geq k~

~0 \leq k \le n~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.