Задача 2. Мускулистый Василий ≡

Условие

Программист Вася осознал что не может целыми днями сидеть за компьютером, и решил пойти в спортзал. Однако его тренер, когда узнал, что Вася программист, решил сделать ему особенную тренировку. Он сообщает Васе целое число n - количество повторений, а Вася в свою очередь должен рассчитать сколько подходов ему надо сделать.

Выносливость Васи оценивается одним целый числом m и означает сколько повторений он сделает за первый подход. Каждый следующий подход Вася немного устает, и сможет сделать на k повторений меньше, чем в предыдущий подход.

Помогите Васе выяснить, за какое наименьшее количество подходов он выполнит поручение тренера. Если Вася окончательно устанет прежде, чем справится с задачей, выведите -1.

Формат входных данных

Первая строка входного файла содержит 3 числа: n - количество повторений, m - количество повторений в первом подходе, k - снижаемое количество повторений.

Формат выходных данных

Выходной файл должен содержать одно единственное число - минимальное количество подходов или -1, если такое невозможно.

Ограничения

0 < N ≤ 10¹⁸

0 ≤ K ≤ M ≤ 10⁹

Система оценки и описание подзадач

Баллы за подзадачи начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Примеры тестов

10 4 1

4

100 50 20

-1

Разбор

~60 баллов O(n)

Просчитаем каждый подход Васи через цикл.

На каждой итерации проверяем, что Вася может сделать подход (количество повторений в подходе положительное).

Отдельно рассматриваем случай, когда k = 0, так как это значительно сокращает время работы на некоторых тестах.

100 баллов O(1)

Используя формулу арифметической прогрессии выводим формулу с неизвестным количество подходов.

После преобразований формула превращается в многочлен 2 степени (ax² + bx + c ≤ 0).

Решаем уравнение, находим 2 корня. Из них нужно выбрать наименьший положительный. Если таких нет, то -1.

Если дискриминант lt 0, то -1. Если k = 0, то отдельно просчитываем ceil(n / m).