Новый интернет-провайдер предоставляет услугу доступа в интернет с посекундной тарификацией. Для подключения нужно купить карточку, позволяющую пользоваться интернетом определенное количество секунд. При этом компания продает карточки стоимостью 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
В турнире по хоккею участвовало 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
N вражеских кораблей движутся прямолинейно с постоянными скоростями. Вакуумная бомба уничтожает все объекты в радиусе R от точки взрыва (то есть все объекты, расстояние от которых до точки взрыва не больше R). Взрывать бомбу можно только в целые моменты времени.
Требуется определить, за какое наименьшее количество взрывов можно уничтожить все корабли, а также в какие моменты времени и в каких точках для этого следует произвести взрывы. Время отсчитывается от момента, когда координаты движущихся кораблей были определены со спутника.
В первой строке входных данных задаются целые числа N (2 <= N <= 10) и R (0 < R ≤ 50. В следующих Nстроках содержится по 4 числа, описывающих движение кораблей. Первые два числа строки – координаты корабля в момент времени 0, по модулю не превосходящие 105. Следующие два числа – значения координат вектора скорости, по модулю не превосходящие 1000. Все эти числа целые.
Гарантируется, что никакие 2 корабля не имеют одинаковые векторы скорости.Однако вполне возможно, что в какой-то момент времени два корабля пройдут через одну точку.
В первой строке выведите одно число – минимальное количество взрывов K. В следующих K строках для каждого взрыва выведите по три числа: целое время взрыва и вещественные координаты взрыва, указанные с точностью не менее трех значащих цифр после точки. Разрешается производить взрывы как в разные, так и в один и тот же момент времени. Разрешается взрывы производить как в различных точках, так и в одной точке в разные моменты времени.
Если решений несколько, выведите любое из них.
Комментарий. Решения, верно работающие при N ≤ 3, будут набирать не менее 50 баллов.
3 3 -3 3 1 0 0 -6 0 2 -8 6 4 -1
1 3 2.000 1.500
2 1 -4 -4 2 2 2 2 -2 -2
2 0 -4.0000 -4.0000 0 2.0000 2.0000