images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
21/11/2024 20:41:02

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

838. Интернет

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (1)

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

Пример ввода

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\ ≤\ 100000`, будут набирать не менее 50 баллов.
Московская городская олимпиада школьников по информатике, 2008
loading