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

Добавлена: 16.04.2026
Обновлена: 16.04.2026
Предмет: Экономика
Автор: Кэмп

#Экономико-математическое моделирование
#Теория игр и принятие финансовых решений

Условие:

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

Родители разрешили Пете пользоваться интернетом M секунд. Определите, за какую наименьшую сумму он сможет купить карточки, которые позволят ему пользоваться интернетом не менее M секунд. Естественно, Петя может купить как карточки различного достоинства, так и несколько карточек одного достоинства.

Формат ввода

В первой строке содержится единственное натуральное число M (1 ≤ M ≤ 109109). Во второй строке задаются натуральные числа a0a0, a1a1, …, a30a30, не превосходящие 109109.

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

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

Пример
Ввод
11
1 1 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Вывод

5

Решение:

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

Шаги решения:

Дано:
- Число $M$ — требуемое количество секунд.
- Массив цен на карточки $a_0, a_1, \ldots, a_{30}$ , где $a_i$ — цена карточки, позволяющей пользоваться интернетом $2^i$ секунд.
Найти:
- Минимальную сумму, которую нужно потратить для получения не менее $M$ секунд.
Решение:
- Начнем с наибольшей карточки и будем использовать её, по...