Новый интернет-провайдер предоставляет услугу доступа в интернет с посекундной тарификацией. Для подключения нужно купить карточку, позволяющую пользоваться интернетом определенное количество секунд. При этом компания продает карточки стоимостью 1, 2, 4,

8 октября 2025
Экономика

Условие:

Новый интернет-провайдер предоставляет услугу доступа в интернет с посекундной тарификацией. Для подключения нужно купить карточку, позволяющую пользоваться интернетом определенное количество секунд. При этом компания продает карточки стоимостью 1, 2, 4, …, 2³0 рублей на a0, a1, a2, …, a30 секунд соответственно.
Родители разрешили Пете пользоваться интернетом M секунд. Определите, за какую наименьшую сумму он сможет купить карточки, которые позволят ему пользоваться интернетом не менее M секунд. Естественно, Петя может купить как карточки различного достоинства, так и несколько карточек одного достоинства.
Формат ввода:
В первой строке содержится единственное натуральное число M (1 ≤ M ≤ 10⁹).
Во второй строке задаются натуральные числа a0, a1, a2, …, a30, не превосходящие 10⁹

Формат вывода:
Выведите единственное число — наименьшую сумму денег, которую Пете придется потратить.

Решение:

Для решения задачи мы можем использовать жадный алгоритм. Мы будем поочередно выбирать карточки с наибольшим количеством секунд, пока не достигнем или не превысим требуемое количество секунд M. При этом мы будем отслеживать стоимость каждой карточки и суммировать затраты. Вот шаги, которые мы будем выполнять: 1. Считываем значение M и массив цен карточек. 2. Создаем список пар, где каждая пара состоит из количества секунд и соответствующей стоимости. 3. Сортируем этот список по количеству секунд в порядке убывания. 4. Итерируемся по отсортированному списку и выбираем карточки, пока не достиг...

- Мы создаем список , который содержит пары для каждой карточки. - Затем сортируем этот список по количеству секунд в порядке убывания. - В цикле мы проверяем, сколько карточек нам нужно для достижения или превышения M секунд, и добавляем соответствующую стоимость к . - В конце выводим общую стоимость. Этот алгоритм работает эффективно, так как количество карточек фиксировано (31), и мы можем обрабатывать их за линейное время относительно их количества.