26/04/2024 16:36:13

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

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

Пример вывода

Решения, верно работающие при `M\ ≤\ 100000`, будут набирать не менее 50 баллов.
Московская городская олимпиада школьников по информатике, 2008

17/03/2008	Школьные сборы, дорешивание (3F)
20/03/2008	Школьные сборы, день 3 (F)
12/02/2014	Занятие 13 (B)