2020-08-05
157
ограничение времени на тест: 2 сек.
ограничение памяти на тест: 65536 KB.
ввод: input.txt
вывод: output.txt
Как известно, в Берляндии традиционно любят эксперименты, поэтому здесь постоянно идет строительство и реконструкция исследовательских лабораторий. В одной из таких лабораторий, специализирующейся на выводе новых видов бактерий, работает небезызвестный ученый Нии Берпастер. Он руководит проектом по выращиванию штамма особого вида палочковых микроорганизмов под названием... Гм. Берпастер решил назвать их отрезковыми.
Помещенные в очень узкую пробирку отрезковые бактерии наблюдаются через микроскоп. После нескольких наблюдений ассистент профессора Берпастера, по совместительству программист БрЦНИТ (Берляндский Центр Новейших Информационных Технологий), построил упрощенную модель эволюции этих бактерий. В модели организмы представлены как отрезки, центры которых лежат на одной прямой (для определенности на оси OX) и которые перпендикулярны этой прямой. При этом процесс поедания (ах, да! эти бактерии крайне агрессивны) бактерий друг другом выглядит как наложение большего отрезка на меньший отрезок, то есть бактерия может съесть другую, только если ее длина не меньше длины жертвы. После пожирания длина отрезка-агрессора увеличивается на единицу. Итак, ассистент расположил отрезки в ряд. Теперь ему интересно, каких максимальных размеров сможет достичь самая левая бактерия, если она будет пытаться пожирать подряд бактерии, находящиеся справа от нее. Как только справа от пожирающей бактерии оказывается бактерия, которую проглотить нельзя, процесс останавливается. Остальные бактерии предполагаются неспособными быть агрессорами, то есть они не способны поедать другие бактерии.
Входные данные
Во входном файле в первой строке дано натуральное число N (1 ≤ N ≤ 1000). Далее в N строках по одному в строке даны длины бактерий: натуральные числа, не превосходящие 1000. Бактерии нумеруются слева направо с единицы.
Выходные данные
Необходимо вывести максимальную длину первой бактерии.
Пример
Ввод
Пример 1
3
5
4
6
Пример 2
5
4
4
1
7
5
Вывод
Пример 1
7
Пример 2
6
Спасти Васю
ограничение времени на тест: 2 сек.
ограничение памяти на тест: 65536 KB.
ввод: input.txt
вывод: output.txt
У Васи большие проблемы. В наказание за прогул урока алгебры учительница задала Васе сложное задание на дом. Дан двучлен вида ax + b, его надо возвести в степень k, а после этого вычислить сумму его коэффициентов. Вася возвел двучлен в квадрат и получил: a2x2 + 2abx + b2.
Дальше - гораздо сложнее. Вася совсем уже было отчаялся, но вовремя вспомнил, что у него есть вы! А у вас есть компьютер и 5 часов рабочего времени.
Входные данные
В первой строке входного файла записаны три целых числа a, b и k (1 ≤ a, b ≤ 100, 1 ≤ k ≤ 20).
Выходные данные
В первой строке выходного файла выведите одно число - сумму коэффициентов исходного двучлена после возведения в степень k.
Пример
Ввод
Пример 1
1 2 2
Вывод
Пример 1
9
Усилители
ограничение времени на тест: 2 сек.
ограничение памяти на тест: 65536 KB.
ввод: input.txt
вывод: output.txt
Для питания своей машины времени ученому-самоучке Шурику необходимо получить напряжение, в N раз превосходящее напряжение бытовой сети (которое равно 1 Бервольту). Для этой цели он решил использовать усилители напряжения. В расположенном неподалеку магазине электроники оказались в продаже два типа усилителей, работающих следующим образом: если у первого усилителя на входе напряжение X Бв, то на выходе 2 X -1 Бв; если у второго усилителя на входе напряжение X Бв, то на выходе 2 X +1 Бв. Усилителей в магазине неограниченное количество. Шурик может последовательно соединять усилители, то есть входом первого усилителя в цепи является бытовая розетка, входом каждого последующего усилителя является выход предыдущего, а с выхода последнего усилителя снимается напряжение для питания машины времени. Усилители стоят одинаково, но недешево, поэтому Шурик хочет обойтись как можно меньшим их числом. Помогите ему.
Входные данные
Во входном файле записано целое число N от 1 до 2*109.
Выходные данные
Если можно собрать схему, описанную в условии, выведите в первой строке минимальное число усилителей в ней, а во второй строке выведите последовательность типов использованных усилителей в цепи от бытовой розетки до машины времени. Выводите "1", если использован усилитель первого типа, и "2", если второго. Числа разделяйте пробелами. Если решения не существует, выведите "No solution".
Пример
Ввод
Пример 1
5
Вывод
Пример 1
2
2 1
