Автор задачі: | Богдан Фейса |
Задачу підготував: | Богдан Фейса |
Розбір написав: | Павло Ціцей |
Припустимо, що всі нові зіграні ігри — це перемоги, оскільки в іншому випадку відсоток виграшу знизиться. Отже, нам потрібно знайти мінімальне , таке що \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}, то відповідь не перевищує , а в іншому випадку відповідь більша за .