НачалоПодразделы
Другие разделы
| 837. Сортировка таблицы |
| 839. Турнир |
| 840. Морской бой |
Дата и время
17/11/2024 01:16:06
838. Интернет
Интернет
Бинарный поискОлимпиадные задачи на русском языке
| 17/03/2008 | Школьные сборы, дорешивание (3F) |
| 20/03/2008 | Школьные сборы, день 3 (F) |
| 12/02/2014 | Занятие 13 (B) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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
Московская городская олимпиада школьников по информатике, 2008
