Мафія у Потоколяндії#138

Мафія у Потоколяндії (Editorial)

Спершу порахуємо, скільки слів напишуть тестувальників.

Кожен пише привітання з слів у загальний чат — разом x \cdot a слів. Крім того, кожен пише кожному іншому тестувальнику повідомлення з слів. Упорядкованих пар «хто кому» рівно x(x-1), тому в особистих чатах буде x(x-1) \cdot b слів.

Отже, загальна кількість слів для тестувальників дорівнює

f(x) = a x + b x (x - 1).

Треба знайти найменше , за якого f(x) \ge n.

Функція строго зростає при x \ge 1 (обидва доданки зростають), тому підходить двійковий пошук по відповіді: шукаємо найменше у діапазоні від до якоїсь свідомо достатньої межі, для якого f(x) \ge n.

Головна технічна пастка — переповнення. Значення у процесі пошуку може сягати мільярдів, а x(x-1)b — зростати квадратично, тому проміжний добуток легко вискакує навіть за межі 64-бітного типу. Є два надійні способи: рахувати в ширшому типі (наприклад, __int128 у C++) або перевіряти умову без множення — порівнюючи з межею через ділення. У Python цієї проблеми немає взагалі.

Складність — від розміру діапазону пошуку.