06/04/2025 15:27:21

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

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

Задачи

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

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

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

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

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

Задачи

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)