Алгоритмы

Женя получил письмо от Леши со словесным описанием схемы метро в его городе. Метро содержит одну кольцевую линию. Каждая из остальных линий пересекается с кольцевой не более чем в двух местах, причем в точках пересечения организованы пересадочные станции. В одном месте кольцевую линию могут пересекать сразу несколько линий, имеющих общую пересадочную станцию.

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

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

Помогите Жене написать программу, которая будет проверять, действительно ли может существовать схема метро, соответствующая полученному описанию.

На рисунке приведена возможная схема метро, соответствующая второму примеру.

Формат входных данных
В первой строке содержится число \(k\) — количество линий метро в городе (\(1 \le k \le 10\)). Все линии пронумерованы от 0 до \(k - 1\), кольцевая линия имеет номер 0. Во второй строке записано число \(n\) — количество пересадочных станций. Каждая из следующих \(n\) строк описывает линии, пересекающиеся на соответствующей пересадочной станции, причем сначала следуют описания пересадочных станций, расположенных на кольцевой линии, в порядке их расположения на ней. Описание каждого узла начинается с количества пересекающихся в нем линий, затем следуют номера линий.

Формат выходных данных
Выведите слово YES, если по описанию можно построить схему метро, и NO в противном случае.

Вася пишет новую версию своего офисного пакета <<Closed Office>>. Недавно он начал работу над редактором <<Dword>>, входящим в состав пакета.

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

Документ в формате редактора <<Dword>> представляет собой последовательность абзацев. Каждый абзац представляет собой последовательность элементов — слов и рисунков. Элементы одного абзаца разделены пробелами и/или переводом строки. Абзацы разделены пустой строкой. Строка, состоящая только из пробелов, считается пустой.

Слово — это последовательность символов, состоящая из букв латинского алфавита, цифр, и знаков препинания: <<.>>, <<,>>, <<:>>, <<;>>, <<!>>, <<?>>, <<->>, <<’>>.

Рисунок описывается следующим образом: <<(image параметры рисунка)>>. Каждый параметр рисунка имеет вид <<имя=значение>>. Параметры рисунка разделены пробелами и/или переводом строки. У каждого рисунка обязательно есть следующие параметры:

Документ размещается на бесконечной вверх и вниз странице шириной \(w\) пикселей (разбиение на конечные по высоте страницы планируется в следующей версии редактора). Одна из точек на левой границе страницы условно считается точкой с ординатой равной нулю. Ордината увеличивается вниз.

Размещение документа происходит следующим образом. Абзацы размещаются по очереди. Первый абзац размещается так, что его верхняя граница имеет ординату 0.

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

Слова размещаются следующим образом. Считается, что каждый символ имеет ширину \(c\) пикселей. Перед каждым словом, кроме первого во фрагменте, ставится пробел шириной также в \(c\) пикселей. Если слово помещается в текущем фрагменте, то оно размещается на нем. Если слово не помещается в текущем фрагменте, то оно размещается в первом фрагменте текущей строки, расположенном правее текущего, в котором оно помещается. Если такого фрагмента нет, то начинается новая строка, и поиск подходящего фрагмента продолжается в ней. Слово всегда <<прижимается>> к верхней границе строки.

Размещение рисунка зависит от его расположения относительно текста.

Если расположение рисунка относительно текста установлено в <<embedded>>, то он располагается так же как слово, за тем исключением, что его ширина равна ширине, указанной в параметрах рисунка. Кроме того, если высота рисунка больше текущей высоты строки, то она увеличивается до высоты рисунка (при этом верхняя граница строки не перемещается, а смещается вниз нижняя граница). Если рисунок типа <<embedded>> не первый элемент во фрагменте, то перед ним ставится пробел шириной \(c\) пикселей. Рисунки типа <<embedded>> также прижимаются к верхней границе строки.

Если расположение рисунка относительно текста установлено в <<surrounded>>, то рисунок размещается следующим образом. Сначала аналогично находится первый фрагмент, в котором рисунок помещается по ширине. При этом перед рисунком этого типа не ставится пробел, даже если это не первый элемент во фрагменте.

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

Если расположение рисунка относительно текста установлено в <<floating>>, то рисунок размещается поверх текста и других рисунков и никак с ними не взаимодействует. В этом случае у рисунка есть два дополнительных параметра: <<dx>> и <<dy>> — целые числа, задающие смещение в пикселях верхнего левого угла рисунка вправо и вниз, соответственно, относительно позиции, где находится верхний правый угол предыдущего слова или рисунка (или самой левой верхней точки первой строки абзаца, если рисунок — первый элемент абзаца).

Если при размещении рисунка таким образом он выходит за левую границу страницы, то он смещается вправо, так, чтобы его левый край совпадал с левой границей страницы. Аналогично, если рисунок выходит за правую границу страницы, то он смещается влево, чтобы его правый край совпадал с правой границей страницы.

Верхняя граница следующего абзаца совпадает с более низкой точкой из нижней границы последней строки и самой нижней границы рисунков типа <<surrounded>> предыдущего абзаца.

По заданным \(w\), \(h\), \(c\) и документу найдите координаты верхних левых углов всех рисунков в документе.

Формат входных данных
Первая строка содержит три целых числа: \(w\), \(h\) и \(c\) (\(1 \le w \le 1000\), \(1 \le h \le 50\), \(1 \le c \le w\)).

Далее следует документ. Размер входного файла не превышает 1000 байт. Гарантируется, что ширина любого слова и любого рисунка не превышает \(w\). Высота всех рисунков не превышает \(1000\). Относительное смещение всех рисунков типа <<floating>> не превышает \(1000\) по абсолютной величине.

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

K участникам сборов для решения было предложено K задач. Участники решили разделить задачи между собой, решить каждому по одной задаче, а затем обменяться решениями (они не учли, что система ejudge способна отследить данный факт J). Известно ориентировочное время, за которое каждый из участников сборов может решить каждую из предложенных задач.

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

Входные данные
Во входном файле сначала записано число K (0 < K < 101) и далее K2 неотрицательных целых чисел, не превосходящие 20000, описывающих матрицу K x K, времен решения каждым из участников каждой из задач.

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

Выведите координаты наиболее удаленной от начала координат точки.

Входные данные
Программа получает на вход набор точек на плоскости. Сначала задано количество точек n, затем идет последовательность из n строк, каждая из которых содержит два числа: координаты точки. Величина n не превосходит 100, все исходные координаты – целые числа, не превосходящие 10³
по абсолютной величине.

Выходные данные
Выведите  координаты точки, наиболее удаленной от начала координат.

Напишите рекурсивную функцию, возводящую число a в степень n. Гарантируется, что все числа "помещаются" в стандартные вещественные (a и ответ) и целые (n) типы.

Входные данные
Вводится 2 числа - a и n (число n может быть отрицательным).

Выходные данные
Необходимо вывести  значение aⁿ

Будем называть числа круглыми, если они содержат в своей записи только цифры 0 и 5. Составим последовательность неотрицательных целых круглых чисел в порядке возрастания: 0, 5, 50, 55, 500, 505 и так далее.

Написать программу, которая находит K-е по порядку в этой последовательности круглое число.

Входные данные
Вводится одно натуральное число K- номер круглого числа в порядке возрастания.

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

В финал конкурса Киноакадемии вышли \(n\) лучших кинофильмов 2014 года. В конкурсе награждаются фильмы в двух номинациях: лучшая режиссура и лучший сценарий. По правилам конкурса в каждой номинации должен быть награжден ровно один фильм, причём в разных номинациях — разные фильмы.

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

Требуется написать программу, которая по результатам опросов определяет наибольший суммарный уровень ликования, которого можно добиться выбором фильмов для награждения в указанных номинациях.

Формат входных данных
В первой строке задано целое число \(n\) — количество кинофильмов, участвующих в финале конкурса Киноакадемии. В следующих \(n\) строках содержатся по три целых числа \(a_i\), \(b_i\), \(c_i\) — уровень ликования, если \(i\)-й фильм не выиграет ни в одной из номинаций, уровень ликования, если этот фильм выиграет в номинации на лучшую режиссуру, и уровень ликования, если этот фильм выиграет в номинации на лучший сценарий.

Формат выходных данных
Первая строка  должна содержать одно число — наибольший возможный суммарный уровень ликования. Вторая строка должна содержать два целых числа — номера фильмов-победителей в номинациях лучшая режиссура и лучший сценарий соответственно. Фильмы нумеруются натуральными числами от 1 до \(n\). Если оптимальных способов выбора награждаемых фильмов несколько, можно вывести любой из них.

 

В приведенном примере наибольший суммарный уровень ликования равен \(3 + 5 + 9 = 17\).

Профиль Уральских гор задается ломаной (x₁, y₁), (x₂, y₂), …, (x_N, y_N), для координат вершин которой верны неравенства x₁ < x₂ < … < x_N. Начальные и конечные точки профиля расположены на уровне моря (y₁ = y_N = 0).

На горном профиле заданы две различные точки A и B, между которыми требуется проложить дорогу. Эта дорога будет проходить по склонам гор и проектируемому горизонтальному мосту, длина которого не должна превышать L. Оба конца моста находятся на горном профиле. Дорога заходит на мост с одного конца и выходит с другого. Мост не может содержать точек, расположенных строго под ломаной (строительство тоннелей не предполагается).
Возможные примеры расположения моста                                                                   Невозможное расположение моста


Достоверно известно, что строительство такого моста в данной местности возможно, причем позволит сократить длину дороги из точки A в точку B. Требуется написать программу, которая определит такое расположение горизонтального моста, что длина дороги от точки A до точки B будет наименьшей.

Формат входных данных
Первая строка входных данных содержит два целых числа N и L — количество вершин ломаной (2 ≤ N ≤ 100 000) и максимальную длину моста (1 ≤ L ≤ 10⁶) соответственно. Вторая строка  содержит координаты точки A, третья строка — координаты точки B. Точки A и B различны.

Последующие N строк содержат координаты вершин ломаной (x₁, y₁), (x₂, y₂), …, (x_N, y_N). Координаты вершин ломаной, а также точек A и B, задаются парой целых чисел, не превосходящих по абсолютному значению 106. Гарантируется, что x₁ < x₂ < … < x_N и y₁ = y_N = 0, а также, что точки A и B принадлежат ломаной.

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

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

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

Требуется написать программу, которая назначит каждой станции тарифный номер.
 

	4 станции, 3 перегона: 1-4, 2-4, 3-4 Маршруты: 1-4-2, 2-4-3, 3-4-1.   Ответ: решения нет
	5 станций, 4 перегона: 1-5, 2-5, 3-5, 4-5 Маршруты: 1-5-2, 2-5-3, 3-5-4, 4-5-1.   Ответ: решение есть; например, следующее: номер станции: 1 2 3 4 5 тарифный номер: 1 4 1 5 3   Замечание: тарифные номера разных станций могут совпадать.

Формат входных данных

В первой строке входных данных содержатся два целых числа: N — количество станций (2 ≤ N ≤ 100 000), и M — количество перегонов между ними (1 ≤ M ≤ N – 1). В последующих M строках записаны пары целых чисел a, b (a ≠ b, 1 ≤ a ≤ N, 1 ≤ b ≤ N), означающие наличие перегона между станциями a и b. За ними в отдельной строке записано единственное целое положительное число K — количество маршрутов электричек. В последующих K строках идут описания маршрутов электричек, по одному на строке. Каждое описание представляет собой последовательность целых чисел — номеров всех станций маршрута в порядке одного из двух возможных направлений следования электрички. Описание маршрута заканчивается числом 0.

Все номера станций в описании маршрута различны. Количество станций в каждом маршруте не менее двух. Любые две последовательные станции в маршруте каждой электрички соединены перегоном. Суммарное количество станций в описаниях всех маршрутов не превосходит 200 000. Могут быть станции и перегоны, через которые не проходит ни одна электричка.
 

Формат выходных данных 

В первую строку выведите «NO», если искомого назначения тарифных номеров не существует. В противном случае в первую строку выведите «YES», а в следующей строке — N целых положительных чисел, где i-е число — тарифный номер i-й станции. Тарифный номер каждой станции должен находиться в диапазоне от 1 до N.

Если существует несколько решений, необходимо вывести любое из них.

Король Полигонии Трианг IV помешан на реформах. Чтобы войти в мировую историю, он решил провести территориальную реформу в своей стране. Страна Полигония имеет форму простого многоугольника, то есть ее граница не имеет самопересечений и самокасаний. В Полигонии большую роль играют внутренние диагонали — отрезки, соединяющие вершины государственной границы и полностью проходящие по территории страны, не касаясь границы. При этом форма Полигонии такова, что никакие две внутренние диагонали не лежат на одной прямой.

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

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

Формат входных данных

В первой строке входных данных задается число N (3 ≤ N ≤ 20) — количество вершин многоугольника, образующего границу Полигонии. В следующих N строках находятся по 2 целых числа, по абсолютной величине не превосходящих 10 000 — координаты вершин в порядке обхода многоугольника против часовой стрелки. Гарантируется, что никакие три последовательные вершины многоугольника не лежат на одной прямой, и он не имеет самопересечений и самокасаний. Также гарантируется, что никакие две диагонали, содержащиеся внутри многоугольника, не лежат на одной прямой.

Формат выходных данных

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

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

В каждую из следующих K строк выведите 4 целых числа — координаты начала и конца соответствующей диагонали разбиения, полностью лежащей внутри многоугольника и не проходящей по его границе.

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

 

Примеры

№	Входные данные	Выходные данные	Рисунок к тесту
1	4 0 0 1 0 1 1 0 1	2 1 1 1 0 0
2	10 -6 0 0 2 6 0 3 3 6 4 2 4 0 6 -2 4 -6 4 -3 3	4 3 2 4 -2 4 0 2 3 3 -3 3 0 2

Известный математик Соломон В. Голомб предложил название полимино для связной фигуры, вырезанной из клетчатой бумаги по линиям сетки. Фигура называется связной, если из любой ее клетки можно добраться в любую другую, переходя из клетки в клетку через их общую сторону. Шахматист, добавил Голомб, сказал бы, что из любой клетки полимино можно дойти ладьей в любую другую. На рис. 1 приведены примеры восьми полимино. Саша увлекается полимино. Для своих экспериментов она вырезает новое полимино из бумаги в клеточку или из старых полимино, оставшихся после предыдущих попыток. Далеко не всегда из старого полимино (рис. 2а, слева) можно вырезать новое (рис. 2а, справа). Поэтому Саша может перед вырезанием нового полимино разделить каждую клетку старого полимино на K² одинаковых квадратных клеток меньшего размера (см. рис. 2б, здесь K = 2).  

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

Например, на рис. 2б приведены все возможные способы вырезания полимино, приведенного на рис. 2а, при K = 2.

Напишите программу, которая ответит на интересующий Сашу вопрос.

Формат входных данных

Первая строка входных данных содержит число K (1 ≤ K ≤ 10 000).

Далее следуют описания двух полимино, сначала нового, затем старого. Каждое полимино задается следующим образом — в первой строке описания задаются размеры H (высота) и W (ширина) минимально возможного прямоугольника, в котором можно разместить данное полимино. Следующие Н строк содержат по W символов описания клеток. При этом клетка, входящая в полимино, обозначается символом « X» (прописная латинская буква «икс»), а не входящая — символом «.» (точка). Количество клеток в каждом полимино не превышает 300.

Формат выходных данных

Выведите одно число — количество различных способов вырезать заданное новое полимино из старого, каждая клетка которого разбита на K² клеток.

Маленький Влад решил создать собственную компьютерную игру. Игра будет проходить на карте, состоящей из комнат, соединённых коридорами. По каждому коридору можно будет передвигаться в обе стороны. Кроме того, Влад планирует создать карту, в которой коридоров будет ровно на один меньше, чем комнат, а также между любой парой комнат можно будет пройти, используя только коридоры. Для того, чтобы пройти игру, игроку необходимо выполнять квесты.

Все квесты в игре имеют одинаковую структуру. Пусть на карте расположены \(m\) комнат. Тогда каждый квест задаётся парой комнат \(u\) и \(v\) (\(1 \le u \le v \le m\)). Для прохождения этого квеста игроку нужно переместиться из комнаты \(u\) в комнату \(v\). Для усложнения игры в каждой комнате, через которую пройдёт игрок (включая начальную и конечную комнату) необходимо решить загадку. Влад называет сложностью квеста минимальное количество загадок, которые надо решить, чтобы его пройти. В частности, сложность квеста, у которого начальная и конечная комната совпадает, равна \(1\), а сложность квеста, в котором начальная и конечная комнаты соединены коридором равна \(2\). Также Влад называет квест трудным, если не существует квеста с большей сложностью, чем данный.

Интересностью игры Влад называет количество трудных уровней. Влад решил создать игру с интересностью ровно \(n\). Поскольку Владу сложно придумывать новые загадки, помогите ему составить карту с минимальным числом комнат, которое может быть в игре с интересностью \(n\).

Формат входных данных
В первой строке задано целое число \(n\) (\(1 \le n \le 500\)) — требуемое количество трудных уровней.

Формат выходных данных
В первой строке выведите целое число \(m\) — минимальное количество комнат на карте.

В следующих \(m - 1\) строках выведите через пробел пары целых чисел \(u\) и \(v\), обозначающие коридор, между комнатами \(u\) и \(v\).

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

Примечание
В первом примере карта выглядит так:

На этой карте есть 10 квестов. Обозначим за (u, v) квест, который начинается в комнате с номером u и заканчивается в комнате с номером v. Сложность квестов (1, 1), (2, 2), (3, 3) и (4, 4) равна 1, сложность квестов (1, 2), (1, 3) и (1, 4) равна 2, а сложность квестов (2, 3), (2, 4) и (3, 4) равна 3. Таким образом, трудными квестами являются квесты (2, 3), (2, 4) и (3, 4). Трудных квестов 3, значит интересность игры на данной карте равна 3.

Во втором тестовом примере карта выглядит так:

На этой карте есть 4 трудных квеста (2, 5), (2, 6), (3, 5) и (3, 6). Их сложность равна 4.

В третьем тестовом примере карта выглядит так:

На этой карте есть 5 трудных квестов (2, 8), (3, 8), (4, 8), (5, 8), (6, 8) со сложностью 4.

В сети магазинов <<Мир>> при оплате карточкой Weeza действует акция. При оплате покупки, состоящей не менее чем из \(10\) товаров, плата за самый дешевый товар не берется. Если товаров не меньше 20, то не оплачиваются уже два самых дешевых товара и т.д.

Например, при одновременной покупке \(17\) товаров, покупатель потратит сумму денег равную стоимости только \(16\) самых дорогих из них, а при покупке \(20\) и \(37\) товаров придется заплатить только за \(18\) и \(34\) самых дорогих товара, соответственно.

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

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

Формат входных данных
В первой строке находится одно число \(n\) (\(1 \leq n \leq 100\,000\)) — количество дисков на ленте.

Следующая строка содержит \(n\) чисел \(a_i\) (\(1 \leq a_i \leq 10^9\)) — стоимости дисков в порядке расположения на ленте.

Формат выходных данных
Выведите наименьшую возможную стоимость покупки всех дисков с учетом акции при оптимальном разбиении дисков на группы.

В первом примере Мише в любом случае придется оплатить все диски, так как суммарное количество товаров меньше \(10\).

Во втором тестовом примере оптимально во время первой покупки оплатить первые два диска, а за остальные диски заплатить во время второй покупки. Тогда не придется заплатить за диск стоимостью \(9\).

Федок очень хочет купить себе комплексный обед в столовой, но сделать это не так просто. В столовой работает всего одна касса, и то очень медленно. На данный момент в очереди находится \(n\) \((2 \leq n \leq 100\,000)\) людей, а сам Федок находится на \(k-\)ой \((1 \leq k \leq n)\) позиции в ней. И вот, чтобы занять себя в этой очереди, Федок стал обдумывать коварный план как побыстрее оплатить комплексный обед и начать есть.

В чем состоит коварный план? Федок хочет крикнуть, что открылась новая касса. Тогда, по его мнению, многие уйдут из очереди в поисках этой кассы, а он приблизится к заветной еде. Но вот в чем проблема: не все люди так нетерпеливы как наш герой. Проще говоря, у каждого человека есть свой параметр \(P_i\) — терпеливость. Если человек стоит на позиции \(x\) и его терпеливость равна \(y\), то он уйдет искать новую кассу только в том случае, если \(y < x\)

Казалось бы, эта задача трудна, но и Федок не глуп. Он своим метким взором определил терпеливости всех людей, стоящих в очереди кроме него. Увы, так как людей очень много, в его голове все перепуталось, и некоторые числа поменялись местами. Таким образом наш герой получил некоторую перестановку множества терпеливости всех людей в очереди \(P_1, P_2, \ldots, P_{n-1}\)

Федок не знает точно, кто насколько терпелив и боится, что не сдвинется в очереди после реализации своей задумки. Поэтому он просит вас помочь ему узнать, какую минимальную и максимальную позицию от начала очереди он может занимать после того как крикнет: <<Свободная касса!>>

Формат входных данных
В первой строке входных данных находится число людей в очереди \(n\) (\(2 \leq n \leq 100\,000\))

Во второй строке находится число \(k\) (\(1 \leq k \leq n\)) — текущая позиция Федка в очереди

В следующей строке содержатся \(n-1\) число — перестановка множества терпеливостей людей в очереди \((0 \leq P_i \leq n)\)

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

Во второй строке выведите максимальное место, которое может стать у Федка после применения его плана

• Решения, работающие для \(n \leq 10\) будут набирать не менее 5 баллов

• Решения, работающие для \(n \leq 1000\) будут набирать не менее 10 баллов

Пояснение к первому тесту:

Алексей стоит на второй позиции. Перед ним один человек.

Если его терпеливость будет равна нулю, то он уйдет, и Федок станет первым

Если же его терпеливость равна трем, то он не уйдет, и Федок останется второй

В гостинице для жирафов администрация хочет запастись подушкам так, чтобы удовлетворить потребности любого своего возможного постояльца. Известно, что жирафам в зависимости от длины их шеи нужно сложить стопку подушек (в стопке одна или несколько подушек) толщиной от \(1\) до \(n\) сантиметров. При этом администрация хочет обойтись как можно меньшим числом подушек, а среди наборов подушек, удовлетворяющих этим требованиям, администрация выберет набор минимальной суммарной толщины, чтобы он занимал минимальный объём в шкафу.

Помогите администрации составить нужный набор подушек, позволяющий получить стопку любой высоты от \(1\) до \(n\) сантиметров включительно.

Формат входных данных
Во входных данных записано единственное целое число \(n\) — максимально возможная длина шеи жирафа (\(1 \leq n \leq 10^9\)).

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

Замечание

В примере из условия необходимо подобрать такой набор из минимального числа подушек, чтобы используя данные подушки удавалось сложить стопку любой целочисленной толщины от \(1\) до \(9\) см. Таким набором является набор из подушек толщиной \(1\), \(2\), \(3\), \(3\) см. Действительно, стопку толщины \(1\), \(2\), \(3\) см можно сложить из одной подушки. Оставшиеся числа получены так: \(4=1+3\), \(5=2+3\), \(6=3+3\), \(7=1+3+3\), \(8=2+3+3\), \(9=1+2+3+3\). Возможны и другие варианты ответа с тем же количеством подушек и их суммарной толщиной. Выполнить условие задачи, используя только три подушки, нельзя.

В ходе работы над оптимизацией компилятора для процессора из предыдущей задачи в фирме Хардсофт задумались об автоматическом выборе подпрограмм, которые станут инлайнподпрограммами. Инлайн-подпрограммы - это такой способ сборки машинного кода, при котором тело подпрограммы во время компиляции подставляется непосредственно в место её вызова, и оно становится частью вызывающего кода. Таким образом, исключаются накладные расходы на вызов и завершение подпрограмм во время работы. 
Инженеры фирмы Хардсофт считают, что инлайн-подпрограммами надо делать те, которые вызываются чаще всего. Однако вставка кода больших подпрограмм в места их вызова приведёт к резкому увеличению памяти, потребляемой программами, а для фирмы важна возможность лёгкой адаптации своего решения к промышленным устройствам, в которых значительную роль играет экономическая составляющая: в частности, необходимый для работы объём памяти должен быть минимальным.
Разработчики создали специальный анализатор, который определяет среднее количество запуска подпрограмм и размер каждой из них.
Требуется определить, какие из подпрограмм можно встроить в инлайн-режиме, для увеличения быстродействия и в пределах доступной памяти.

Формат входных данных
в первой строке через пробел указаны натуральные числа N, M и X. N и M не превышают 100 и являются количеством подпрограмм и количеством цепочек вызова, а X не превышает 10⁶ и является количеством памяти (в килобайтах), доступным для размещения инлайнподпрограмм. Далее идёт N строк, где через пробел перечислены имена подпрограмм (из латинских слов длиной до 20 символов) и их размер в килобайтах (натуральное число от 1 до 1000). Далее - M строк с описанием выявленных цепочек вызова: в них записаны имена подпрограмм через пробел, после которых также через пробел указано ожидаемое количество срабатываний этой цепочки за время работы программы (целое число от 1 до 1000).
Формат выходных данных
в первой строке - количество подпрограмм, которые можно пометить инлайновыми, в последующих строках - имена этих подпрограмм в том порядке, в котором они были указаны во входных данных. Требуется выбрать подпрограммы так, чтобы количество вызовов инлайн-подпрограмм за время работы программы было максимальным. 

Теплым весенним днем группа из N школьников-программистов гуляла в окрестностях города Кисловодска. К несчастью, они набрели на большую и довольно глубокую яму. Как это случилось — непонятно, но вся компания оказалась в этой яме.

Глубина ямы равна H. Каждый школьник знает свой рост по плечи h_i и длину своих рук l_i. Таким образом, если он, стоя на дне ямы, поднимет руки, то его ладони окажутся на высоте h_i + l_i от уровня дна ямы. Школьники могут, вставая друг другу на плечи, образовывать вертикальную колонну. При этом любой школьник может встать на плечи любого другого школьника. Если под школьником i стоят школьники j₁, j₂, …, j_k, то он может дотянуться до уровня h_j1 + h_j2 + … + h_jk + h_i + l_i.

Если школьник может дотянуться до края ямы (то есть h_j1 + h_j2 + … + h_jk + h_i + l_i ≥ H), то он может выбраться из нее. Выбравшиеся из ямы школьники не могут помочь оставшимся.

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

Формат входных данных
В первой строке входных данных задается натуральное число N (1 ≤ N ≤ 2000) — количество школьников, попавших в яму.

Далее в N строках содержится по два целых числа: рост i-го школьника по плечи h_i (1 ≤ h_i ≤ 10⁵) и длина его рук l_i (1 ≤ l_i ≤ 10⁵).

В последней строке указано целое число — глубина ямы H (1 ≤ H ≤ 10⁵).

Формат выходных данных
В первой строке выведите K — максимальное количество школьников, которые смогут выбраться из ямы. Если K > 0, то во второй строке в произвольном порядке выведите их номера, разделяя их пробелами. Школьники нумеруются с единицы в том порядке, в котором они заданы во входных данных. Если существует несколько решений, выведите любое.

Банк «Кисловодск» переходит на новый вид банковских карт. Для этого производятся одинаковые заготовки, на которых есть специальное место для идентификации клиента. Изначально на этом месте записывается кодовое число X. В банке с помощью специального прибора можно стирать некоторые цифры числа X. Оставшиеся цифры, будучи записанными подряд, должны образовывать номер счета клиента. Например, при X = 12013456789 номера счетов 5, 12, 17 или 12013456789 получить можно, а номера 22 или 71 получить нельзя.

Способ распределения номеров счетов в банке очень прост. Счетам присваиваются последовательно номера 1, 2, … Очевидно, что при таком способе в какой-то момент впервые найдется номер счета N, который нельзя будет получить из цифр X указанным выше способом. Руководство банка хочет знать значение N.

Напишите программу, которая находила бы N по заданному X.

Формат входных данных
Вводится натуральное число X без ведущих нулей (1 ≤ X ≤ 101000). 

Формат выходных данных
Выведите искомое N без ведущих нулей.

Вася из задачи A по-прежнему занят поиском кладов. Более того, у него появились последователи. Один из таких последователей попросил Васю помочь в своих поисках. Так, по карте сокровищ Васю просят восстановить кратчайший путь до клада. Конфигурация лабиринта совпадает с конфигурацией, описанной в задаче A (поле \(N \times M (1 \le N, M \le 100, N \times M \le 100))\), в одной клетке которого находится клад, в K
 клетках находятся входы в лабиринт).

Требуется вывести искомый путь.

Формат входных данных
Первая строка содержит 2 числа N<=100 и M<=100, задающие размеры лабиринта. Далее следует описание лабиринта: N
 строк по M символов в каждой. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с сокровищем (такая клетка в лабиринте ровно одна).
В (N+2)-й строке находится число \(K (1 \le K \le N \times M)\) - количество входов в лабиринт. Далее в K строках содержатся координаты входов. Так, в i-й строке содержатся числа \(x_i\) и \(y_i\), означающие, что i-й вход расположен в \(x_i\)-й строке и в \(y_i\)-м столбце \((1 \le x_i \le N, 1\le y_i \le M)\). Гарантируется, что координаты входов попарно различны, и то, что все входы расположены в пустых клетках. Ни один из входов не находится в клетке с сокровищем.

Формат выходных данных
В первой строке вывести одно число - длину кратчайшего маршрута. В следующих строках необходимо вывести кратчайший маршрут. Каждую клетку маршрута (включая начальную и конечную) вывести на отдельной строке в формате \(x_i\) \(y_i\), где \(x_i\)  - строка клетки, а \(y_i\)  - столбец клетки.

Если существует несколько путей минимальной длины, выведите любой. Если до сокровища невозможно добраться, в единственной строке выведите -1.

Примеры

№	Входные данные	Выходные данные
1	5 5 00000 00000 10*00 01111 00000 4 1 1 1 5 4 1 5 5	4 1 1 2 1 2 2 3 2 3 3
2	3 3 010 1*1 010 4 1 1 1 3 3 1 3 3	-1

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

К сожалению, для полноценного изучения языка недостаточно только одного словаря: кроме англо-латинского необходим латинско-английский. За неимением лучшего он решил сделать второй словарь из первого.

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

Помогите Васе выполнить работу по созданию латинско-английского словаря из англо-латинского.

Формат входных данных
В первой строке содержится единственное целое число \(N\) (\(1 \le N \le 100\)) — количество английских слов в словаре. Далее следует \(N\) описаний. В первой строке каждого описания содержится английское слово. В следующей строке записано единственное число \(K \ge 1\) — количество переводов. В следующих \(K\) строках приведены переводы текущего английского слова на латинский, по одному в каждой строке.

Все слова состоят только из маленьких латинских букв. Общее количество слов на входе не превышает \(100\). Длина каждого слова не превосходит 15 символов.

Формат выходных данных
Выведите соответствующий данному латинско-английский словарь в следующем формате. В первую строку запишите единственное целое число \(N\) — количество латинских слов в словаре. Далее выведите \(N\) описаний, каждое описание в отдельной строке: сначала латинское слово, затем отделённый пробелами дефис (символ номер 45), затем разделённые запятыми с пробелами переводы этого латинского слова на английский.

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