Страница: 1 Отображать по:
#713
Интернет
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Карточки стоят 1, 2, 4, ..., 2^30 рублей. Для каждой карточки задано ai - сколько секунд доступа в интернет она предоставляет. Можно покупать несколько карточек одного достоинства. Требуется определить минимальную цену покупки не менее M секунд доступа.

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

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

Входные данные

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

Выходные данные

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

Решения, верно работающие при M ≤ 100000 , будут набирать не менее 50 баллов.

Примеры
Входные данные
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
#714
Турнир
  
За победу команда получает 2 очка, за ничью - 1, за поражение - 0. По известным результатам команд требуется восстановить турнирную таблицу.

В турнире по хоккею участвовало K команд, каждая сыграла с каждой по одному матчу. За победу команда получала 2 очка, за ничью – 1, за поражение – 0 очков.

Известно, сколько очков в итоге получила каждая команда, однако результаты конкретных матчей были утеряны. Требуется восстановить одну из возможных турнирных таблиц.

Входные данные

В первой строке входных данных содержится одно натурально число K, не превосходящее 100 – количество команд. Во второй строке  задаются  через пробел K целых неотрицательных чисел, не превосходящих 2(K–1), – количество очков, набранных командами, занявшими первое, второе, …, K-е места соответственно (то есть каждое следующее число не больше предыдущего).

Выходные данные

Выведите турнирную таблицу в следующем формате. Таблица должна состоять из K строк с результатами игр команд, занявших первое, второе, …, последнее место (команды, набравшие одинаковое число очков, могут быть расположены в таблице в любом порядке). В каждой строке должно быть записано K чисел через пробел – количество очков, набранных в игре данной команды с первой, второй, … командами соответственно. Количество очков – это число 0, 1 или 2. В клетках на главной диагонали (соответствующих не существующей игре команды "самой с собой") нужно записать нули.

Гарантируется, что входные данные соответствуют реальному турниру, то есть хотя бы одна таблица, соответствующая входным данным, может быть построена. Если таких таблиц несколько, выведите любую из них.

Примеры
Входные данные
4
6 4 2 0
Выходные данные
0 2 2 2 
0 0 2 2
0 0 0 2
0 0 0 0
Входные данные
4
3 3 3 3
Выходные данные
0 2 0 1
0 0 2 1
2 0 0 1
1 1 1 0
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест