Язык программирования

В данной задаче вам предлагается автоматизировать оценку результата экспресс теста.
Вам дана двухцветная картинка размером 10×20. Для обозначения цветов используются символы «#» и «.». Тест
считается отрицательным, если на картинке изображена одна вертикальная полоска и положительным, если три. В любом
другом случае тест считается испорченным.
Полоской будем считать область картинки 10×k, состоящую из символов «#», где k может быть произвольным. При этом
все соседние клетки с этой областью должны быть «.». Полоска может находиться на границе картинки.

Входные данные
В первой строке входных данных задано число t - число тестов (1 ≤ t ≤ 30). В следующих t⋅10+(t−1) строках заданы картинки
тестов. Соседние картинки разделены пустыми строками. После последней картинки, пустой строки нет.
Каждая картинка состоит из 10 строк по 20 символов, каждый из которых либо «#», либо «.».

Выходные данные
Для каждой картинки выведите результат теста в отдельной строке:
Negative - если тест отрицательный;
Positive - если тест положительный;
Incorrect - если тест испорчен.

 Примеры

№	Входные данные	Выходные данные
1	4 .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... .........#.......... .........##......... .........##......... .........##......... .........##......... .........##......... .........##......... ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..#.......#.....###. ..##......#.....###. ..##......#.....###. ..##......#.....###. ..##......#.....###. ..#.......#.....###. ..#.......#.....###. ..##......#.....###. ..#.......#.....###.	Negative Incorrect Positive Incorrect

Генеалогическое древо — это графическая схема, описывающая родственные связи в пределах одной семьи. Начало такого дерева — это один предок (родоначальник) или супруги и далее цепочка строится вниз. Сопоставим с каждым элементов дерева целое неотрицательное число, называемое высотой.  У самого верхнего предка высота 0, у каждого следующего потомка высота на 1 больше, чем у его родителя. 

По заданному генеалогическому древу, определите высоту всех его элементов.

Входные данные
Программа получает на вход число элементов в генеалогическом древе N. Далее следует N−1 строка, задающие родителя для каждого элемента древа, кроме родоначальника. Каждая строка имеет вид имя_потомка имя_родителя.

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

Программа должна вывести список всех элементов древа в лексикографическом порядке. После вывода имени каждого элемента необходимо вывести его высоту.
 

Пример

№	Входные данные	Выходные данные
1	9 Alexei Peter_I Anna Peter_I Elizabeth Peter_I Peter_II Alexei Peter_III Anna Paul_I Peter_III Alexander_I Paul_I Nicholaus_I Paul_I	Alexander_I 4 Alexei 1 Anna 1 Elizabeth 1 Nicholaus_I 4 Paul_I 3 Peter_I 0 Peter_II 2 Peter_III 2

У игрока в космической стрелялке есть очень мощная лазерная пушка. Но она неподвижна и может стрелять только в одном направлении. Игрок может расставить на игровом поле двусторонние зеркала, меняющие ход луча, чтобы поражать врагов. Введём декартову систему координат с центром, где расположена пушка, то есть пушка имеет координаты (0; 0). Пушка стреляет в направлении точки (1; 1). Игрок может поставить зеркала в точках с целочисленными координатами. Зеркала могут быть горизонтальными или вертикальными, попадание луча в зеркало меняет траекторию луча по законам отражения света. Некоторые возможные варианты отражения луча от зеркала изображены на рисунке.

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

Входные данные
Программа получает на вход два целых числа X и Y , не превосходящих по модулю 10000, записанные в разных строках — координаты цели. Точка (X; Y) не совпадает с началом координат.

Выходные данные
Программа должна вывести в первой строке число N — необходимое количество зеркал. Следующие N строк должны содержать информацию о каждом зеркале. В i-й строке должны быть записаны через пробелы два целых числа xi и yi и один символ ti , обозначающие координаты (xi ; yi) точки, в которых установлено i-е зеркало, и тип этого зеркала ti . Если ti является символом «V», то i-е зеркало размещено вертикально, если же ti является символом «H», то зеркало размещено горизонтально. Например, строка «-2 5 H» обозначает горизонтальное зеркало в точке (−2; 5). Зеркала можно выводить в любом порядке. Зеркало нельзя размещать в точке (0; 0), также нельзя размещать два зеркала в одной точке. Значения xi и yi не должны по модулю превосходить 100 000. Также, разумеется, нельзя допустить, чтобы отражённый луч попал в пушку. Если вариантов ответа несколько, выведите любой из них. Если поразить цель в соответствии с условиями задачи невозможно, программа должна вывести одно число «-1». Если для поражения цели зеркала не нужны, программа должна вывести одно число «0»
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 1	1 3 3 H

В кинотеатре места часто расставляют со сдвигом соседних рядов для удобства зрителей. Пусть в таком кинотеатре N мест в 1-м, 3-м, 5-м и всех нечётных рядах и N + 1 место во 2-м, 4-м и всех чётных рядах. Места в рядах нумеруются от 1 до N в нечётных рядах и от 1 до N + 1 в чётных рядах. Касса продаёт билеты подряд: сначала в 1-й ряд на места с 1-го по N-е, потом — во 2-й ряд на места с 1-го по N + 1-е, затем в 3-й ряд с 1-го места и т.д. Определите номер ряда и номер места для K-го проданного билета.

Входные данные
Программа получает на вход два целых числа. В первой строке записано число N (1 <= N <= 10⁹ ) — количество мест в 1-м ряду кинотеатра. Во второй строке записано число K — порядковый номер проданного билета (1 <= K <= 2 × 10⁹ ).

Выходные данные
Программа должна вывести два числа в одной строке через пробел: номер ряда и номер места K-го проданного билета.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	10 25	3 4	Билеты с 1 по 10 будут проданы в первый ряд. Билеты с 11 по 21 будут проданы во второй ряд. В третий ряд будут проданы билеты, начиная с 22-го, 25-й билет окажется на 4-м месте 3-го ряда.

Коротышки решили взять в полет на Луну либо Незнайку либо Пончика. Не сумев договориться, они решили проголосовать. Незнайка и Пончик наблюдают краткий отчет о голосовании. Коротышки показывают Незнайке и Пончику соотношение текущего количества голосов, полученных Незнайкой и Пончиком, но не фактическое количество голосов. Незнайка и Пончик посмотрели отчет N раз, и когда они смотрели его в i-й (1<=i<=N) раз, соотношение было Pi:Ni. Известно, что Незнайка и Пончик имели хотя бы один голос, когда впервые увидели отчет. Найдите минимально возможное общее количество голосов, полученных Незнайкой и Пончиком, когда они проверили отчет в N-й раз. Можно предположить, что количество голосов, полученных Незнайкой и Пончиком, никогда не уменьшается.

Входные данные
В первой строке задается целое число N (1<=N<=1000). В следующих N строках записано по 2 числа Pi и Ni (1<=P_i,N_i<=1000). Pi и Ni - взаимно простые числа. 

Выходные данные
Выведите минимально возможное общее количество голосов. Гарантируется, что правильный ответ - не более 10¹⁸.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 2 3 1 1 3 2	10	Количество голосов, полученных Пончиком и Незнайкой, изменяется так 2,3 → 3,3 → 6,4. Общее количество голосов в конце составляет 10, что является минимально возможным числом.
2	4 1 1 1 1 1 5 1 100	101	Возможно, что ни Пончик ни Незнайка не получили голосов между моментом, когда они смотрели отчет, и моментом, когда они смотрели его в следующий раз.
3	5 3 10 48 17 31 199 231 23 3 2	6930

Определите трех учащихся с наилучшим средним баллом по трем предметам. Выведите фамилии и имена этих учащихся. Если при этом у нескольких учащихся средний балл совпадает со средним баллом учащегося, "занявшего 3-е место", то необходимо вывести их всех.

Входные данные
Заданы сначала количество учащихся n, затем n строк, каждая из которых содержит фамилию, имя и три числа (оценки по трем предметам: математике, физике, информатике). Данные в строке разделены одним пробелом. Оценки принимают значение от 1 до 5.

Выходные данные
Необходимо вывести пары фамилия-имя по одной на строке, разделяя фамилию и имя одним пробелом. Выводить оценки не нужно. Порядок вывода должен быть таким же, как в исходных данных.
 
 

Примеры

№	Входные данные	Выходные данные
1	3 Yakovlev Ivan 5 5 5 Yapryntsev Aleksey 5 5 5 Kozlov Georgiy 5 5 5	Yakovlev Ivan Yapryntsev Aleksey Kozlov Georgiy

У Громозеки есть следующие два личных принципа: он никогда не преодолевает расстояние больше L за один день. Он никогда не спит под открытым небом. То есть он должен находться в отеле в конце дня.
На планете Блук N отелей и все расположены на одной улице. Координата i-го отеля (1<=i<=N) равна xi.
Путешествуя по планете Блук, Громозека запланировал Q переездов. Каждым переездом он планирует менять отель aj на bj (1<=j<=Q). Для каждого переезда найдите минимальное количество дней, которое нужно Громозеке, чтобы добраться от aj-го отеля до bj-го, следуя его принципам.
Гарантируется, что он всегда может поехать из aj-го отеля до bj-го отеля.

Входные данные
В первой строке задается целое число N (2<=N<=10⁵) - количество отелей на планете Блук. Во второй строке - N чисел xi - координаты i-го отеля (1<=x₁<x₂<...<x_N<=10⁹ , x_i+1−x_i<=L). В третьей строке записано число L (1<=L<=10⁹).  В четвертой строке - число Q (1<=N<=10⁵). 
В последних Q строчках находится по два различных числа aj и bj (1<=a_j,b_j<=N). Все числа целые.

Выходные данные
Выведите Q строк. В j-й строке (1<=j<=Q) должно быть указано минимальное количество дней, которое Громозеке нужно, чтобы добраться из  aj-го отеля до bj -го отеля.

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	9 1 3 6 13 15 18 19 29 31 10 4 1 8 7 3 6 7 8 5	4 2 1 2	По 1-му переезду он может проехать от 1-го отеля до 8-го за 4 дня следующим образом: День 1: Переезд из 1-го отеля во 2-й отель. Пройденное расстояние - 2. День 2: Переезд из 2-го отеля в 4-й. Пройденное расстояние - 10. День 3: Переезд из 4-го отеля в 7-й. Пройденное расстояние - 6. День 4: Переезд из 7-го отеля в 8-й. Пройденное расстояние - 10.

 

Для целых чисел b ( b >= 2 ) и n ( n >= 1 ) пусть функция f(b, n) определяется следующим образом:
\(f (b, n) = n, когда\ n < b \\ f (b, n) = f (b, floor (n / b)) + (n \ mod \ b), когда \ n >= b\)

Здесь
floor(n / b) обозначает наибольшее целое число, не превышающее n / b;
n mod b обозначает остаток от n, деленный на b.

Менее формально f(b, n) равно сумме цифр n, записанных в базе b. Например, справедливо следующее:
\(f (10,87654) = 8 + 7 + 6 + 5 + 4 = 30\\ f (100,87654) = 8 + 76 + 54 = 138\)

Вам даны целые числа n и s. Определите, существует ли целое число b (b >= 2) такое, что f(b, n) = s. Если ответ положительный, найдите наименьшее из таких b.


Входные данные
В первой строке вводится целое число n (1 <= n <= 10¹¹). Во второй строке - целое число s (1 <= s <= 10¹¹).

Выходные данные
Выведите ответ на задачу. Если ответа нет, то выведите -1.
 

 

Примеры

№	Входные данные	Выходные данные
1	87654 30	10
2	87654 138	100
3	87654 45678	-1
4	31415926535 1	31415926535
5	1 31415926535	-1

 

Вам даны два целых числа K и S. Три переменные X, Y и Z принимают целые значения, удовлетворяющие условию \(0<=X,Y,Z<=K\). Сколько существует различных значений X, Y и Z, таких что \(X+Y+Z=S\)?

Входные данные
На вход подается два целых числа K (\(2<=K<=2500\)) и S (\(0<=S<=3\cdot K\)).

Выходные данные
Выведите количество троек X, Y и Z, удовлетворяющих условию.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	2 2	6	Есть шесть троек X, Y и Z, которые удовлетворяют условию: Х = 0, Y = 0, Z = 2 Х = 0, Y = 2, Z = 0 Х = 2, Y = 0, Z = 0 Х = 0, Y = 1, Z = 1 Х = 1, Y = 0, Z = 1 Х = 1, Y = 1, Z = 0
2	5 15	1	Лишь одна тройка удовлетворяют условию задачи: Х = 5, Y = 5, Z = 5

 

В ряд расположены N ящиков. Изначально в i-м ящике слева находится ai конфет.  Громозека выбирает ящик, содержащий хотя бы одну конфету, и съедает одну из конфет в выбранном ящике.Он может выполнять это действие любое количество раз. Его цель добиться того, чтобы в любых двух соседних коробках содержалось не более x конфет.
Найдите минимальное количество операций, необходимых для достижения цели Громозеки.

Входные данные
В первом строке задается два числа N (\(2<=N<=10^5\)) и x (\(0<=x<=10^9\)).  Во второй строке содержится N целых чисел ai (\(0<=a_i<=10^9\)).

Выходные данные
Выведите ответ на задачу.

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 3 2 2 2	1	Необходимо съесть одну конфету во второй коробке. Тогда количество конфет в каждой коробке станет (2,1,2).
2	6 1 1 6 1 2 0 4	11	Например, можно съесть шесть конфет во второй коробке, две в четвертой и три в шестой. Тогда количество конфет в каждой коробке станет (1,0,1,0,0,1).
3	5 9 3 1 4 1 5	0	Цель уже достигнута
4	2 0 5 5	10	Все конфеты должны быть съедены.

 

У Громозеки есть N целых чисел a1,a2,..,aN. Его цель -  получить N равных целых чисел, преобразовав некоторые из них. Он может преобразовать каждое целое число не более одного раза. Преобразование целого числа x в другое целое число y стоит ему \((x-y)^2 \) рублей. Даже если \(a_i = a_j\) (\(i \neq j\)) он должен отдельно оплатить стоимость преобразования каждого из них (см. пример 2). 
Найдите минимальную общую стоимость для достижения цели Громозеки.

Входные данные
В первой строке задается число N (\(1<=N<=100\)). Во второй строке числа a1,a2,..,aN (\(100<=a_i<=100\)).

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

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	2 4 8	8	Минимальная по сумме трансформация обоих чисел - это преобразование каждого числа в 6 будет: (4-6)2+(8-6)2=8 рублей.
2	3 1 1 3	3	Трансформируем все числа в 2: (1-2)2+(1-2)2+(3-2)2=3  рубля. Громозека обязан заплатить \((1-2)^2\) рубля за каждое преобразованное число 1.
3	3 4 2 5	5	Трасформируем 2 и 5 в число 4: (2-4)2+(5-4)2=5 рублей.
4	4 -100 -100 -100 -100	0	Ничего не надо преобразовывать.

 

Новый квест, в котором участники должны выбраться с территории проведения, представляет собой прямоугольник из N × M комнат. Каждая комната имеет четыре двери, ведущие в соседние комнаты, из комнат на краю прямоугольника двери ведут наружу, через эти двери можно
покинуть территорию проведения квеста.
В начале квеста в каждой комнате находится по человеку, а все двери заперты. После начала квеста организаторы дистанционно открывают в каждой комнате запирающий механизм одной из четырёх дверей. Теперь человек, находящийся в этой комнате, может открыть эту дверь и перейти
в соседнюю комнату, через другие три двери выйти из этой комнаты нельзя. При этом может оказаться так, что дверь, соединяющая две комнаты, будет отпираться только с одной стороны, тогда пройти через эту дверь можно только с той стороны, с которой она будет открываться, проходить
через дверь в обратном направлении нельзя, если в соседней комнате будет отперта не эта дверь, а какая-то другая. Если комната находится на краю территории и из этой комнаты открыта дверь наружу, то, пройдя через эту дверь, участник навсегда покидает территорию квеста.
После начала квеста и отпирания дверей участники начинают перемещаться между комнатами. Каждый участник перемещается в соседнюю открытую комнату и продолжает перемещаться до тех пор, пока не покинет территорию квеста. Однако возможна ситуация, когда некоторые участники будут бесконечно перемещаться между комнатами и никогда не выйдут наружу.
Разработчики квеста попросили Вас составить такой план отпирания дверей, при котором ровно K человек смогут выбраться наружу с территории квеста.
Входные данные
Программа получает на вход три числа N, M, K, 1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 0 ≤ K ≤ NM. N и M – количество строк и столбцов в прямоугольном плане квеста, K – количество человек, которые должны выйти из квеста.
Выходные данные
Программа должна вывести план территории квеста в виде N строк, каждая из которых должна содержать M символов. Символ соответствует тому, какая дверь будет открыта в данной комнате и может быть одной из следующих заглавных английских букв: U (дверь в верхнюю по данному плану комнату), D (дверь в нижнюю комнату), L (дверь в левую комнату), R (дверь в правую комнату). Необходимо вывести один любой подходящий план решения задачи. Если ни одного подходящего плана не существует, программа должна вывести одну строчку «IMPOSSIBLE».».
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	1 2 1	IMPOSSIBLE	Территория квеста состоит из 1 строки и 2 столбцов. При любом способе открытия дверей из квеста не сможет выбраться ровно один человек.
2	3 4 5	RDLD ULUR DURU	Территория квеста состоит из 3 строк и 4 столбцов. Из квеста должны выйти 5 человек. На рисунке ниже приведена картинка, соответствующая ответу из примера. Стрелками обозначены открытые двери, точками помечены комнаты, обитатели которых выйдут из квеста.

Среди открытого банка задач ЕГЭ по математике есть следующая: по заданным натуральным числам l, r и m вас просят найти целые числа a, b и c, каждое из которых не меньше l и не больше r, и такие, что будет существовать натуральное число n (целое число, большее нуля) такое, что
n · a + b − c = m.
Паша еще только начал готовиться к ЕГЭ и не совсем понимает, как решать подобную задачу. Помогите ему для разных вариантов этой задачи находить подходящие a, b и c.

Формат входных данных
В единственной строке заданы три целых числа l, r и m (1 ≤ l ≤ r ≤ 500 000, 1 ≤ m ≤ 1010).

Формат выходных данных
Выведите три целых числа a, b и c такие, что l ≤ a, b, c ≤ r и существует такое натуральное число n, что n · a + b − c = m. Гарантируется, что такие числа существуют. Если подходящих решений несколько, выведите любое из них.
 

Примеры

№	Входные данные	Выходные данные
1	4 6 13	4 6 5
2	2 3 1	2 2 3

Замечание
В первом примере можно выбрать n = 3, тогда n · 4 + 6 − 5 = 13 = m. Так же возможны такие ответы: a = 4, b = 5, c = 4 (при этом n = 3); a = 5, b = 4, c = 6 (при этом n = 3); a = 6, b = 6, c = 5 (при этом n = 2); a = 6, b = 5, c = 4 (при этом n = 2).
Во втором примере n = 1, тогда n · 2 + 2 − 3 = 1 = m. Число n = 0 не могло быть выбрано, так как число n обязательно должно быть натуральным.

Сегодня Дима целый день старался и выписывал на длинную бумажную ленту своё любимое целое положительное число n, состоящее из l цифр. К сожалению, лента получилась настолько длинной, что в итоге не влезла в Димин шкаф.

Чтобы справиться с этой неприятностью, Дима решил разрезать ленту на две непустые части, на каждой из которых записано целое положительное число без ведущих нулей, после чего сложить числа, написанные на получившихся частях, а полученную сумму записать на новую ленту.

Дима хочет, чтобы полученное число было как можно меньше, ведь это повышает шансы на то, что хотя бы сумма в шкаф влезет. Помогите Диме определить, какое минимальное число он может получить.

Входные данные
Первая строка содержит одно целое число l (2 ≤ l ≤ 100000) — длину любимого числа Димы.

Вторая строка содержит целое положительное число n, изначально записанное на ленте — любимое число Димы.

Число n состоит ровно из l цифр, при этом запись не содержит ведущих нулей. Также Дима гарантирует, что существует хотя бы один способ разрезать число, удовлетворяющий всем требованиям выше.

Выходные данные
Выведите одно целое число — минимальное число, которое может получить Дима.

Примечание
В первом примере Дима может разрезать число 1234567 на числа 1234 и 567. Их сумма равна 1801.

Во втором примере Дима может разрезать число 101 на числа 10 и 1. Их сумма равна 11.

Примеры

№	Входные данные	Выходные данные
1	7 1234567	1801
2	3 101	11

Наше счастье постоянно — жуй кокосы, ешь бананы, Жуй кокосы, ешь бананы, Чунга-чанга!
м/ф «Катерок»
После открытия острова «Чунга-Чанга» туда постепенно начала пробираться цивилизация и даже стала развиваться рыночная экономика. Появилась и новая валюта — чижик. Теперь для того, чтобы счастливо жевать кокосы, их нужно сначала купить под пальмой.

Саша и Маша проходили мимо пальмы, под которой продаются кокосы по цене z чижиков за штуку. У Саши есть x чижиков, а у Маши y. Каждая из девочек собирается купить максимальное число кокосов, на которое у неё хватит денег. Обсудив планы о покупке кокосов, девочки заметили, что если одна из них передаст какое-то количество чижиков другой, то суммарное количество кокосов, которое они купят, может от этого увеличиться (а может и уменьшиться). Кокосы не продаются по частям, то есть каждая из девочек может купить только целое неотрицательное число кокосов. Чижики тоже не могут быть разделены на части, то есть одна из девочек может передать другой только целое неотрицательное число чижиков.

Например, предположим, что у Саши было 5 чижиков, у Маши 4, а один кокос стоит 3 чижика. Тогда, если девочки не будут обмениваться чижиками, то они купят 1+1=2 кокоса. Если же Маша передаст Саше один чижик, то у Саши их будет 6, а у Маши 3, и девочки купят 2+1=3 кокоса.

Жизнь на острове уже не так легка и проста, поэтому Саша и Маша хотят распределить деньги так, чтобы суммарно купить как можно больше кокосов. При этом, никто не любит одалживать чижики, поэтому среди всех способов, приводящих к максимальному количеству купленных кокосов, найдите тот, который минимизирует число передаваемых между Сашей и Машей (неважно в какую сторону) чижиков.

Входные данные
Первая строка содержит три целых числа x, y и z (0 ≤ x, y ≤ 10¹⁸ , 1 ≤ z ≤ 10¹⁸) — количество чижиков у Саши, количество чижиков у Маши и цена одного кокоса.

Выходные данные
Выведите два целых числа — максимальное суммарное количество кокосов, которое можно купить, и минимальное количество чижиков, которым для этого придётся поделиться одной из девочек.
Примечание
Первый пример разобран в условии задачи. Во втором примере оптимально не обмениваться чижиками, в таком случае будет куплено 3+4=7 кокосов.

Примеры

№	Входные данные	Выходные данные
1	5 4 3	3 1
2	6 8 2	7 0

Широко известна следующая задача для младших школьников. Три черепахи ползут по дороге. Одна черепаха говорит: “Впереди меня две черепахи”. Другая черепаха говорит: “Позади меня две черепахи”. Третья черепаха говорит: “Впереди меня две черепахи и позади меня две черепахи”. Как такое может быть? Ответ: третья черепаха врет!

По дороге одна за другой движутся N черепах. Каждая черепаха говорит фразу вида: “Впереди меня a_i черепах, а позади меня b_i черепах”. Ваша задача определить самое большое количество черепах, которые могут говорить правду.

Входные данные
В первой строке вводится целое число N (1 ≤ N ≤ 10000) . Далее следуют N строк, содержащих целые числа ai и bi, по модулю не превосходящие 10000, описывающие высказывание i-ой черепахи.

Данные о высказываниях черепах приведены в произвольном порядке, то есть первое высказывание не обязательно соответствует черепахе, идущей во главе колонны, второе - не обязательно следующей за ней и так далее

Выходные данные
Выведите целое число M – максимальное количество черепах, которые могут говорить правду.
 

Примеры

№	Входные данные	Выходные данные
1	3 2 0 0 2 2 2	2

У ювелира есть весы с двумя чашками, он может определять равны ли массы грузов, лежащих на двух чашках, а если не равны – то на какой чашке лежит более лёгкий груз.

Масса ювелирного изделия, которую нужно определить ювелиру, является целым числом от 1 до N. Ювелир должен запасти набор гирек (их массы также должны быть целыми числами), используя которые ювелир может определить любую возможную массу от 1 до N. Для определения массы ювелир может производить любое число взвешиваний, может использовать все гирьки или только некоторые из них, может класть гирьки на разные чашки весов.

Определите набор гирек, содержащий минимальное возможное число гирек, используя который можно определить любую возможную целочисленную массу от 1 до N.

Программа получает на вход натуральное число N (2 ≤ N ≤ 10⁸) – максимально допустимую массу ювелирного изделия.

Программа должна вывести несколько натуральных чисел, не превосходящих 10⁹, – массы гирек в минимальном требуемом для решения задачи наборе (допускается использовать гирьки массой, больше, чем N, если их масса не превосходит 10⁹).

Если задача имеет множество решений, необходимо вывести любое из них.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3	2	Пусть x – изделие, массу которого необходимо определить. Нужно на одну чашу весов положить x, а на другую чашу весов – гирьку в 2. Если x будет легче, то x = 1, при равенстве – x = 2, если x тяжелее, то x = 3.
2	5	3 4	Покажем, как при помощи гирек в 3 и 4 определить все массы от 1 до 5. Массы 3 и 4 можно определить при помощи равенств x = 3 и x = 4. Массу 1 можно определить при помощи равенства x + 3 = 4 (на одну чашу кладется изделие и гирька массой 3, на другую чашу – гирька массой 4). Массу 2 можно определить, например, по условию x < 3 (на одну чашу весов кладется изделие, на другую – гирька массой 3), а также проверив при помощи ранее описанного алгоритма, что x ≠ 1 . Массу 5 можно определить при помощи взвешивания x > 4.

Мы все знаем, что начавшаяся зима скоро закончится, и на праздновании Масленицы все будут есть блины. Об этом и будет наша задача.

N гостей сидят за столом, и перед каждым стоит тарелка с блинами. На тарелке i-го гостя лежит ai блинов. Каждый гость съедает один блин за одну минуту, таким образом, время, когда закончит есть блины последний человек, равно наибольшему значению из ai.

Неожиданно к ним присоединился ещё один человек, и теперь все присутствующие могут переложить часть своих блинов (в том числе могут переложить все свои блины, а могут не перекладывать ни одного блина) вновь пришедшему человеку. Перекладывание блинов происходит одновременно и моментально.

Гости хотят переложить блины таким образом, чтобы после перекладывания они съели все блины за минимальное время (которое равно наибольшему числу блинов на тарелках у гостей, включая нового гостя). Определите, за какое наименьшее время гости смогут съесть свои блины после перекладывания.

Программа получает на вход натуральное число N, не превосходящее 100.000, – первоначальное количество гостей. Следующие N строк содержат натуральные числа a_i – количество блинов на тарелке i-го человека. Значения a_i даны в порядке неубывания, то есть a_i ≤ a_i+1. Сумма значений всех a_i не превосходит 2·10⁹.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 1 3 5 6	4	За столом сидят 4 человека, у них на тарелках 1, 3, 5, 6 блинов. Новому гостю последний гость отдаст 2 блина, а предпоследний – 1 блин, и тогда у всех, включая нового гостя, будет не более 4 блинов.

На Новом проспекте построили подряд 10 зданий. Каждое здание может быть либо жилым домом, либо магазином, либо офисным зданием.

Но оказалось, что жителям некоторых домов на Новом проспекте слишком далеко приходится идти до ближайшего магазина. Для разработки плана развития общественного транспорта на Новом проспекте мэр города попросил вас выяснить, какое же наибольшее расстояние приходится преодолевать жителям Нового проспекта, чтобы дойти от своего дома до ближайшего магазина.

Входные данные
Программа получает на вход десять чисел, разделенных пробелами. Каждое число задает тип здания на Новом проспекте: число 1 обозначает жилой дом, число 2 обозначает магазин, число 0 обозначает офисное здание. Гарантируется, что на Новом проспекте есть хотя бы один жилой дом и хотя бы один магазин.

Выходные данные
Выведите одно целое число: наибольшее расстояние от дома до ближайшего к нему магазина. Расстояние между двумя соседними домами считается равным 1 (то есть если два дома стоят рядом, то между ними расстояние 1, если между двумя домами есть еще один дом, то расстояние между ними равно 2 и т.д.)

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 0 1 1 0 1 0 2 1 2	3	В примере из условия дальше всего идти до ближайшего магазина жителям четвертого дома: ближайший к их дому магазин находится в первом доме, и им нужно пройти три дома до него. Жителям других домов придется пройти меньшее расстояние до ближайшего магазина, поэтому ответ 3.

Лавочки в парке устроены следующим образом. Несколько одинаковых кубических гранитных блоков ставятся в ряд, а на них кладется гранитная плита (см. рисунок). Архитектор-модернист решил, что будет интереснее, если у всех лавочек расположение гранитных блоков-ножек будет разным (и не обязательно симметричным). При этом они располагаются так, чтобы плита не падала: для этого достаточно, чтобы и слева, и справа от центра плиты был хотя бы один гранитный блок или его часть (в частности, если центр плиты приходится на середину какого-нибудь блока, то и слева, и справа от центра плиты находится часть блока, и плита не падает).

Грабители обнаружили, что можно по одному вытаскивать гранитные блоки, находящиеся с краю (как слева, так и справа). Они хотят вытащить из-под лавочки как можно больше блоков так, чтобы она при этом не упала (передвигать оставшиеся блоки нельзя). Определите, какие блоки они должны оставить.


Входные данные
В первой строке входных данных содержатся два числа: L - длина лавочки и K - количество гранитных блоков-ножек. Оба числа натуральные и не превышают 10 000.

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

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

Примеры

№	Входные данные	Выходные данные
1	5 2 0 2	2
2	13 4 1 4 8 11	4 8
3	14 6 1 6 8 11 12 13	6 8