Информатика

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

Вася, ярый любитель кино и столь же ярый ненавистник математики, первым купил билет на очередную премьеру. Когда Вася вошёл в зал и сел на своё место, он увидел, что все остальные кресла в его ряду ещё пустуют. Вася точно знал, что к началу сеанса зал заполнится до отказа, а это значило, что с минуты на минуту о его ноги начнут спотыкаться другие кинолюбители, пробирающиеся к своим местам. Несмотря на всю свою нелюбовь к математике, Вася мгновенно оценил, какое максимальное количество человек может спотнуться о его ноги, прежде чем все зрители займут свои места. А вы сможете?

Входные данные: Программа получает на вход два целые числа (по одному в строке) n и k — количество мест в том ряду, где сидит Вася, и номер его места соответственно (1≤k≤n≤50, n — чётно). Места в ряду нумеруются с единицы.

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

№	Входные данные	Выходные данные
1	4 1	1

Палиндромом называется слово, которое одинаково читается как слева направо, так и справа налево, например, в английском языке такими словами являются «radar» и «racecar».
Света изучает английский язык и решила принять участие в дистанционном конкурсе знатоков английского языка. Но, когда она писала ответ на задание «найдите самое длинное слово, которое является палиндромом», ошиблась и нажала на клавиатуре одну лишнюю клавишу.
Определите, какую букву нужно удалить в набранном Светой слове, чтобы это слово стало палиндромом.

Входные данные
Программа получает на вход строку из строчных английских букв, содержащую не менее 2 и не более 100 000 символов.

Выходные данные
Программа должна вывести единственное число – номер буквы в строке, при удалении которой слово становится палиндромом. Если при удалении любой буквы слово не станет палиндромом, программа должна вывести число 0.

Примеры

№	Входные данные	Выходные данные
1	raceczar	6
2	car	0

Напишите рекурсивную функцию, которая выбирает из полученной последовательности квадраты целых чисел и выводит их в обратном порядке. Использовать массив для хранения последовательности не разрешается. Запрещено использовать циклы. 
Основная программа должна содержать вызов функции и вывод результата

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

Выходные данные:  Программа должна вывести элементы полученной последовательности, которые представляют собой квадраты целых чисел, в обратном порядке в одну строчку, разделив их пробелами. Если таких нет, программа должна вывести число 0.

Примеры

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

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

Входные данные: Входная строка содержит два вещественных числа – координаты точки на плоскости (сначала x -координата, затем – y -координата).

Выходные данные: Программа должна вывести слово 'YES', если точка попала в заштрихованную область, и слово 'NO', если не попала.

 

Примеры

№	Входные данные	Выходные данные
1	0.5 0.5	YES
2	-0.5 -0.5	NO

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

Входные данные: Входная строка содержит два вещественных числа – координаты точки на плоскости (сначала x -координата, затем – y -координата).

Выходные данные: Программа должна вывести слово 'YES', если точка попала в заштрихованную область, и слово 'NO', если не попала.

 

Примеры

№	Входные данные	Выходные данные
1	0. 0.	NO

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

Входные данные: Входная строка содержит два вещественных числа – координаты точки на плоскости (сначала x -координата, затем – y -координата).

Выходные данные: Программа должна вывести слово 'YES', если точка попала в заштрихованную область, и слово 'NO', если не попала.

 

Примеры

№	Входные данные	Выходные данные
1	0. 1.	NO
2	0. -1.	YES

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

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

Входная строка содержит два вещественных числа – координаты точки на плоскости (сначала x -координата, затем – y -координата).

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

Программа должна вывести слово 'YES', если точка попала в заштрихованную область, и слово 'NO', если не попала.

 

Примеры

№	Входные данные	Выходные данные
1	0. 1.	YES
2	0. -1.	NO

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

Входные данные: Входная строка содержит два вещественных числа – координаты точки на плоскости (сначала x -координата, затем – y -координата).
Выходные данные: Программа должна вывести слово 'YES', если точка попала в заштрихованную область, и слово 'NO', если не попала.

Примеры

№	Входные данные	Выходные данные
1	1.5 0.25	YES
2	1.5 -0.25	NO

Давным-давно цены на билеты были такими:
1 поездка — 15 рублей,
5 поездок — 70 рублей,
10 поездок — 125 рублей,
20 поездок — 230 рублей,
60 поездок — 440 рублей.
Пассажир планирует совершить n поездок. Определите, сколько билетов каждого вида он должен приобрести, чтобы суммарное количество оплаченных поездок было не меньше n, а общая стоимость приобретенных билетов — минимальна.

Входные данные: Программа получает на вход одно число n.

Выходные данные: Программа должна вывести пять целых чисел: количество билетов на 1, 5, 10, 20, 60 поездок, которое необходимо приобрести. Если для какого-то данного n существует несколько способов приобретения билетов одинаковой суммарной стоимости, необходимо вывести ту комбинацию билетов, которая дает большее число поездок.

Примеры

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

В часах села батарейка, и они стали идти вдвое медленнее. Когда на часах было x1 часов y1 минут, правильное время было a1 часов b1 минут. Сколько времени будет на самом деле, когда часы в следующий раз покажут x2 часов y2 минут?

Входные данные Программа получает на вход числа x1, y1, a1, b1, x2, y2 в указанном порядке. Все числа целые. Числа x1, a1, x2 — от 0 до 23, числа y1, b1, y2 — от 0 до 59. Все числа вводят по одному в строке

Выходные данные Выведите два числа a2 и b2, определяющие сколько будет времени на самом деле, когда на часах будет x2 часов y2 минут. Числа выводить в одной строке через пробел
 

№	Входные данные	Выходные данные
1	12 34 10 34 12 35	10 36

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не менее, чем 4 (разница в индексах элементов пары должна быть 4 или более, порядок элементов в паре неважен). Необходимо определить максимальную сумму пары чисел кратную 112, при этом первый элемент пары должен быть больше второго (\(a[i] > a[j]\), \(i < j\)).

Входные данные
В первой строке входных данных задаётся количество чисел N (\(5 <= N <= 1000\)). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.


Входные данные
Программа должна вывести в первой строке одно число: максимальную сумму пары элементов, находящихся в последовательности на расстоянии не менее чем 4, в которых сумма элементов кратна 112, а во второй строке – числа, образующие пару, через пробел. Если ни одной подходящей пары нет, нужно вывести одно число –1.
 

Примеры

№	Входные данные	Выходные данные
1	7 119 62 343 50 48 105 274	224 119 105

Входные данные
В первой строке входных данных задаётся количество чисел N (\(1 < N <= 10000\)). В каждой из последующих N строк записано одно целое неотрицательное число, не превышающее 10000.

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

Примеры

№	Входные данные	Выходные данные
1	7 1 0 2 0 5 0 8	9

Ася очень любит животных. Недавно она приобрела n котят, дала им числовые идентификаторы от 1 до n и поселила в вольере. Вольер представляет собой ряд из n ячеек, также пронумерованных от 1 до n. Cоседние ячейки разделены сетчатыми перегородками, всего в вольере n−1 перегородок. Изначально в каждой ячейке поселился ровно один котёнок с некоторым номером.

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

В i-й день Ася делала следующее.

Обращала внимание, что какие-то котята x_i и y_i, в i-й день живущие в соседних ячейках, хотят играть.
Удаляла перегородку между этими ячейками, превращая их в одну, в которой оказывались все котята из двух прежних ячеек.
Поскольку Ася не возвращала перегородки, через n−1 день вольер стал единой ячейкой, в которой обитали все котята. Будучи очень педантичной, Ася записывала в специальный журнал идентификаторы котят x_i  и y_i  для каждого из n−1 дней.

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

Входные данные
В первой строке задано целое число n (\(2 \leq n \leq 150000\)) — количество котят.

В следующих n−1 строках заданы пары целых чисел x_i , y_i  ( \(1 \leq x_i, y_i, \leq n,x_i \neq y_i\) ) — идентификаторы котят, между ячейками которых была удалена перегородка в день i. Гарантируется, что котята xi  и yi  не находятся в одной ячейке по итогам предыдущих объединений ячеек.

Выходные данные
Выведите n различных целых чисел p_i (\(1 \leq p_i \leq n\)), где p_i — идентификатор котёнка, который изначально жил в ячейке с номером i. Если возможных вариантов ответа несколько, выведите любой из них.

Примечание
В ответе к примеру приведено одно из возможных изначальных расселений котят, существуют и другие варианты ответа. На изображении ниже показано, как происходило объединение ячеек для этого варианта исходного размещения котят. Обратите внимание, что при таком размещении котята, подружившиеся в каждый из дней согласно журналу Аси, находятся в соседних ячейках.

 

Ввод	Вывод
5 1 4 2 5 3 1 4 5	3 1 4 2 5

Вам дано описание дорожной сети страны. Ваша задача – найти длину кратчайшего пути между городами А и B.

Формат входных данных
Сеть дорог задана во входном файле следующим образом: первая строка содержит числа N и K (1<=N<=100000, 0<=K<=300000), где K – количество дорог. Каждая из следующих K строк содержит описание дороги с двусторонним движением – три целых числа ai, bi и li (1aibiN, 1li106). Это означает, что имеется дорога длины li, которая ведет из города ai в город bi. В последней строке находятся два числа А  и В  – номера городов, между которыми надо посчитать кратчайшее расстояние (1<=A,B<=N )

Формат выходных данных
Вы должны вывести в выходной файл единственное число – расстояние между требуемыми городами. Если по дорогам от города А  до города В  доехать невозможно, выведите –1.