Инженерный тур. 1 этап

Задача 1.1.(100 баллов)

Кредиты

Тема: жадные алгоритмы

Условие

Михаил задумал купить автомобиль и решил сначала посоветоваться со своим другом Сергеем. Сам Михаил хотел купить новый китайский автомобиль Халва, а его друг Сергей предложил купить старый немецкий БНВ. После долгих обсуждений Михаил принял решение купить оба автомобиля. Для этого ему потребовалось много денег, из-за чего Михаил набрал много «кредитов с подвохом».

Подвох таких кредитов в том, что в отличие от обычных, они устроены как накопительный счет, но только наоборот. То есть каждый месяц задолженность увеличивается на несколько процентов от текущей задолженности. Например, если Михаил взял в кредит с подвохом 10 рублей под 5 процентов, то на следующий месяц он будет должен уже 10,5 рублей, а через месяц — 11,025 рублей при условии, что Михаил не пытался выплачивать долг. Выплата долга происходит раз в месяц, до пересчета величины долга. Размер выплаты может быть любым, не обязательно целым числом.

Помогите Михаилу определить, сколько он в итоге потратит на погашение кредитов при оптимальной стратегии выплат, если каждый месяц у него есть фиксированная сумма денег, которую Михаил может потратить на выплаты долгов. Гарантируется, что кредиты можно выплатить за 2024 месяца.

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

Первая строка содержит натуральное число \(N\) (\(1 \leqslant N \leqslant 100\)) — число взятых кредитов.

Далее следуют \(N\) строк. Каждая \(i\)-я из этих строк содержит два целых числа \(d_i\) и \(p_i\) (\(1 \leqslant d_i \leqslant 1000\), \(0 \leqslant p_i \leqslant 100\)) — размер задолженности по \(i\)-му кредиту и ежемесячный процент.

Последняя строка содержит одно целое число \(M\) (\(1 \leqslant M \leqslant 1000\)) — сколько Михаил может суммарно тратить в месяц на погашение задолженностей.

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

Выведите одно вещественное число — ответ на задачу. Он будет засчитан, если абсолютная или относительная погрешности не превышают \(10^{-6}\).

Тестовые данные

Номер теста	Стандартный ввод	Стандартный вывод
1	3 1 1 2 2 3 3 4	6.03

Решение

Оптимальной будет стратегия выплаты кредитов по убыванию процентов. Для вычисления общей суммы требуется проэмулировать помесячный процесс выплаты кредитов. На каждом шаге нужно завести переменную с текущей суммой и вычитать ее из оставшейся суммы кредита.

Для удобства сделаем замену \(p_i' = (1+p_i)\). Рассмотрим две пары индексов \(x\) и \(y\). Предположим, что \(d_x > M\) и \(d_y > M\). Пусть в первый месяц будет произведен платеж за \(x\)-й, а во второй — за \(y\)-й кредит. Тогда после первого месяца общий долг за эти два кредита будет равен: \[(d_x-M) \cdot p_x' + d_y \cdot p_y',\] а после второго: \[(d_x-M) \cdot p_x' \cdot p_x' + (d_y \cdot p_y' - M) \cdot p_y'.\] Раскроем скобки и получим: \[d_x \cdot (p_x')^2 - M\cdot (p_x')^2 + d_y \cdot (p_y')^2 - M \cdot p_y'.\] Если же изменить порядок платежей, то общий долг за эти два кредита будет равен: \[d_x \cdot (p_x')^2 - M \cdot p_x' + d_y \cdot (p_y')^2 - M\cdot (p_y')^2.\] Вычтем первую сумму из второй и получим: \[M\cdot (p_x')^2 + M \cdot p_y' - M \cdot p_x' - M\cdot (p_y')^2= M\cdot (((p_x')^2 - p_x') - ((p_y')^2 - p_y')).\] Так как \(M > 0\) и \(p_i' \geqslant 1\), то разность будет положительной, если \(p_x' > p_y'\).

Следовательно, выгодней выплачивать сначала кредит с наибольшим процентом вне зависимости от текущих задолженностей.

Ниже представлено решение на языке Python.

Python

n = int(input())
d = [0.0] * n
p = [0.0] * n

for i in range(n):
    d[i], p[i] = map(float, input().split())
    
m = float(input())

ans = 0.0

order = list(range(n))
order.sort(key=lambda i: -p[i])

for s in range(2024):
    c = m

    for i in order:
        if c > d[i]:
            c -= d[i]
            d[i] = 0
        else:
            d[i] -= c
            c = 0
    ans += m - c

    for i in range(n):
        d[i] *= (p[i] / 100.0 + 1)

    if c > 0:
        print(ans)
        break