Процент виграшу#371

Процент виграшу (Розбір)

Автор задачі:

Богдан Фейса

Задачу підготував:

Богдан Фейса

Розбір написав:

Павло Ціцей

Припустимо, що всі нові зіграні ігри — це перемоги, оскільки в іншому випадку відсоток виграшу знизиться. Отже, нам потрібно знайти мінімальне , таке що \frac{p+k}{q+k}\ge \frac{a}{b}. Спробуємо розв'язати рівняння. b\cdot (p+k)\ge (q+k)\cdot a. Отже, k\cdot (b-a)\ge q\cdot a-b\cdot p. Тепер ми маємо, що k\ge \frac{q\cdot a-b\cdot p}{b-a}. Зверніть увагу, що задачу також можна розв'язати за допомогою бінарного пошуку. Для цього потрібно наступну ідею: якщо \frac{p+k}{q+k}\ge \frac{a}{b}, то відповідь не перевищує , а в іншому випадку відповідь більша за .