Новый интернет-провайдер предоставляет услугу доступа в интернет с посекундной тарификацией. Для подключения нужно купить карточку, позволяющую пользоваться интернетом определенное количество секунд. При этом компания продает карточки стоимостью 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
Требуется в каждую клетку квадратной таблицы размером NxN поставить ноль или единицу так, чтобы в любом квадрате размера KxK было ровно S единиц.
Во входном файле записаны три числа — N, K, S (1N100, 1KN, 0SK2).
В выходной файл выведите заполненную таблицу. Числа в строке должны разделяться пробелом, каждая строка таблицы должна быть выведена на отдельной строке файла. Если решений несколько, выведите любое из них.
3 2 1
0 0 0 0 1 0 0 0 0
4 2 2
1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0
Магазины в рекламных целях часто устраивают распродажи. Так, например,одна из крупных сетей магазинов канцелярских товаров объявила два рекламных предложения: "купи \(N\) одинаковых товаров и получи еще один товар бесплатно"и "купи \(K\) товаров по цене \(K-1\) товара".
Для проведения олимпиады организаторам требуется распечатать условия для участников, на что уходит очень много бумаги. Каждая пачка стоит \(B\) рублей. Какое максимальное количество пачек бумаги можно приобрести на \(A\) рублей, правильно используя рекламные предложения?
Во входном файле записаны целые числа \(N\), \(K\), \(A\) и \(B\) (\(1\leq N\leq 100\), \(2\leq K\leq 100\), \(1\leq A \leq 10^9\), \(1\leq B \leq 10^9\)), разделенные пробелами.
Выведите одно целое число - максимальное количество пачек бумаги, которое смогут купить организаторы олимпиады.
В первом примере, дважды используя второе рекламное предложение, можно купить 8 пачек бумаги, заплатив за 6.
Во втором примере рекламными предложениями воспользоваться нельзя.
В третьем примере можно по одному разу воспользоваться каждым из двух рекламных предложений и на оставшийся рубль купить еще одну пачку бумаги.
4 4 13 2
8
3 4 8 3
2
3 4 7 1
9