Главная
Библиотека
Экономика
Новый интернет-провайдер предоставляет услугу доступа в интернет с посекундной тарификацией. Для подключения нужно купить...

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

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

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

Условие:

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

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

Решение:

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