Задачник Базовый курс EN

Сколько стоит рассрочка

поиск корня двоичный поиск точность вычислений финансы

Магазин продаёт вещь за S тенге — или в рассрочку: n ежемесячных платежей по P тенге, первый через месяц после покупки. Переплата видна сразу: P · n − S. Но сколько это в процентах годовых? Покупатель, который отдаёт деньги частями, пользуется не всей суммой весь срок, поэтому делить переплату на цену и на число лет неверно.

Честный ответ — эффективная ставка. Найдите месячную ставку r, при которой платежи, приведённые к дню покупки, в сумме дают ровно цену:

$$S = \frac{P}{1 + r} + \frac{P}{(1 + r)^2} + \dots + \frac{P}{(1 + r)^n},$$

и выведите годовую ставку (1 + r)¹² − 1 в процентах.

Вход

В первой строке число предложений q (1 ≤ q ≤ 2000). В каждой из следующих q строк — три целых числа S, P, n (1 ≤ S ≤ 10⁹, 1 ≤ P ≤ 10⁹, 1 ≤ n ≤ 360). Гарантируется, что P · n ≥ S и месячная ставка меньше 40 %.

Выход

Для каждого предложения — годовую эффективную ставку в процентах. Ответ принимается с абсолютной или относительной погрешностью 10⁻⁶.

Примеры

Пример 1

Вход

3
600000 29990 24
480000 40000 12
150000 16500 10

Выход

19.706249
0.000000
23.457163

Ограничения

Время · Python: 4000 мс
Время · Go: 1000 мс
Память: 256 МБ
Проверка: 7 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Формулы для r нет: это корень уравнения степени n. Как ведёт себя правая часть, когда r растёт?

2Подсказка 2

Если ставка растёт, каждый платёж «сегодня» стоит меньше, и сумма убывает. При r = 0 она равна P · n ≥ S. Значит, корень зажат между 0 и любой ставкой, при которой сумма уже меньше S.

3Идея

Приведённая стоимость платежей PV(r) монотонно убывает, поэтому месячную ставку ищем бисекцией на [0, 1]: если PV(середины) больше цены, ставка выше середины, иначе ниже. 80 делений пополам сужают отрезок до 2⁻⁸⁰ — точнее, чем хранит double.

4Разбор

Сумму геометрической прогрессии считаем по формуле PV(r) = P · (1 − (1 + r)⁻ⁿ) / r, но с двумя предосторожностями. При r = 0 формула делит ноль на ноль — это рассрочка без переплаты, и PV = P · n. А при крошечном r разность 1 − (1 + r)⁻ⁿ теряет знаки: из единицы вычитается почти единица. Поэтому считаем её как −expm1(−n · log1p(r)) — функции expm1 и log1p есть и в Python, и в Go и сохраняют точность возле нуля. Так же годовую ставку: expm1(12 · log1p(r)).

Первый пример: телефон за 600 000 тенге в 24 платежа по 29 990. Переплата 119 760, «на глазок» это 10 % в год. Но эффективная ставка — 19,7 %: в среднем покупатель пользуется деньгами магазина лишь половину срока.

Метод Ньютона здесь тоже работает, но требует осторожности: шаг из неудачной точки может уйти в отрицательную ставку, где (1 + r)⁻ⁿ огромно, а у рассрочки без переплаты корень ровно в нуле, где формула делит на ноль.

4+Решение

5Сложность

80 шагов бисекции на предложение, каждый — пара вызовов expm1 и log1p: O(q) с константой около сотни.

6Типичные ошибки

Ньютон без отрезка. Из фиксированного старта и с делением на r он ломается на рассрочке без переплаты — во втором тесте их пять подряд.
Простой процент. (P · n − S) / S / (n/12) — почти вдвое меньше честной ставки в первом же примере.
Мало шагов. Бисекция на [0, 1] до 10⁻⁶ по месячной ставке даёт годовую с ошибкой больше допустимой: погрешность умножается на 12 · (1 + r)¹¹ и на 100 при переводе в проценты.
Сумма прогрессии циклом. Верно, но при n = 360 и 80 шагах это почти 60 миллионов операций на Python.

Алгоритмы задачи

NUM~ Алгоритм Бисекция и метод Ньютона Корень уравнения: деление отрезка пополам надёжно, касательные Ньютона — быстро. бисекция — log₂((b − a)/ε) шагов; Ньютон — около log₂ от числа знаков 2 задачи SRT Приём Двоичный поиск по ответу Если проверить ответ легче, чем найти, и проверка монотонна, — ищем ответ делением пополам. O(log D · стоимость проверки) 2 задачи