Информатика

Петя живёт в Санкт-Петербурге и увлекается метеорологией. Из научного интереса он решил подтвердить или опровергнуть мнение о том, что в Санкт-Петербурге постоянно идёт дождь. Для этого Петя завёл дневник дождя и раз в неделю в воскресенье оставляет в нём запись с информацией о том, идёт ли дождь. Каждую запись Петя подписывает номером текущего дня в месяце, дни в месяце нумеруются с 1 до числа дней в этом месяце (от 28 до 31 в разных месяцах).

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

Формат входных данных
В первой строке вывода даны два целых числа \(n\) и \(m\) (\(1 \le n, m \le 31\)) — номер текущего дня месяца и число, которым подписана запись две недели назад.

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

Выведите единственное число – каким числом должна быть подписана запись неделю назад.

Примеры

6
1 2 3 4 5 6

1 4 3 6 5 2

Планируется строительство новой магистрали <<Урал>>. Долговечность автомагистрали зависит от пластов пород, залегающих под ней. Пластом называется геологическое тело, состоящее из одной горной породы.

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

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

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

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

В \(i\)-й из следующих \(n\) строк содержатся целые числа \(l_i\) и \(r_i\) (\(0 \leqslant l_i < r_i\leqslant 10^9\)) "— расстояния от начала магистрали до точек, под которыми начинается и заканчивается \(i\)-й пласт.

В следующей строке записано целое число \(m\) "— количество скважин, в которых проводилось бурение. Следующие \(m\) строк описывают результаты бурения: в каждой строке сначала указаны два целых числа \(x\) (\(0 \leqslant x \leqslant 10^9\)) и \(k\) (\(0 \leqslant k \leqslant n\)) "— расстояние от начала магистрали до скважины и количество обнаруженных в данной скважине пластов, затем "— целые числа \(s_1, s_2, \ldots, s_k\) "— номера пробуренных пластов, перечисленные в порядке залегания сверху вниз. Скважины перечислены в порядке возрастания расстояния \(x\).

Гарантируется, что решение существует.

Формат выходных данных
Первая строка выходного файла должна содержать \(n\) целых чисел \(p_1, p_2, \ldots , p_n\), описывающих возможный порядок залегания пластов сверху вниз. Среди чисел \(p_1, p_2, \ldots , p_n\) каждый номер пласта должен встретиться ровно один раз. При этом пласт с номером \(p_j\) не должен нигде проходить выше пластов с номерами \(p_1, \ldots ,p_{j-1}\) или ниже пластов с номерами \(p_{j+1}, \ldots , p_n\).

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

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

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

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

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

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

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

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

На пригородной железной дороге 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

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

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

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

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

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

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

Костя и Женя — создатели группы <<Бумага>> — после выпуска легендарного альбома решили создать новое музыкальное объединение <<дневные грузчики>>, для этого им нужно найти двух новых людей.

Они пригласили на кастинг \(n\) человек. Кастинг продлится \(q\) дней. В \(i\)-й из дней Костя и Женя хотят найти двух человек на отрезке с \(l_i\) по \(r_i\), которые больше всего подходят их объединению. Так как <<дневные грузчики>> занимаются современным искусством,  музыкальные навыки им не важны, и они смотрят лишь на внешние признаки: им хочется, чтобы разница роста двух людей была как можно меньше.

Помогите им, и для каждого дня укажите минимальную разницу роста людей с кастинга на данном отрезке!

Формат входных данных
В первой строке вам дано два числа \(n, q\) (\(2 \leqslant n \leqslant 4 \cdot 10^5, 1 \leqslant q \leqslant 10^6\)) — количество людей, которые пришли на кастинг, а также количество дней кастинга.

Во второй строке вам даны \(n\) чисел \(a_1, a_2, a_3, \ldots, a_n\) (\(1 \leqslant a_i \leqslant n\)) — рост каждого из кандидатов.

Также гарантируется, что все \(a_i\) различны.

В следующих \(q\) строках даны по \(2\) числа \(l_i, r_i\) (\(1 \leqslant l_i < r_i \leqslant n\)) — отрезок людей для рассмотрения в \(i\)-й день кастинга.

Формат выходных данных
Выведите \(q\) строк. В \(i\)-й строке должна быть минимальная разница роста между двумя кандидатами на отрезке в \(i\)-й день кастинга.

Примечание
В первом примере минимальная разность на отрезке \([1, 2]\) составляет \(2\) (\(3 - 1 = 2\)), на отрезке \([2, 3]\) – \(1\), на отрезке \([1, 3]\) также \(1\).

В третьем примере минимальную разность на отрезке \([4, 6]\) составляют числа \(3, 5\) (\(5 - 3 = 2\)). На отрезке \([1, 2]\) минимальную разность имеют числа \(2, 6\) (\(6 - 2 = 0\)). На отрезке \([3, 6]\) минимальную разность имеют числа \(1, 3\) (\(3 - 1 = 2\)). На отрезке \([1, 3]\) минимальную разность образуют числа \(1, 2\) (\(2 - 1 = 1\)).

Как вы знаете, девочка Даша постоянно что-то ищет. На этот раз ей дали перестановку, и она хочет найти такой её подотрезок, что ни один из элементов на его концах не является ни минимумом, ни максимумом всего подотрезка. Более формально, вас просят найти такие числа \(l\) и \(r\) \((1 \leqslant l \leqslant r \leqslant n)\), что \(a_l \neq \min(a_l, a_{l + 1}, \ldots, a_r)\), \(a_l \neq \max(a_l, a_{l + 1}, \ldots, a_r)\) и \(a_r \neq \min(a_l, a_{l + 1}, \ldots, a_r)\), \(a_r \neq \max(a_l, a_{l + 1}, \ldots, a_r)\).

Напомнима, что перестановкой длины \(n\) называется массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\), выписанных в произвольном порядке. Например, \([2,3,1,5,4]\) является перестановкой, но \([1,2,2]\) не является перестановкой (\(2\) встречается дважды в массиве) и \([1,3,4]\) тоже не является перестановкой (\(n=3\), но \(4\) присутствует в массиве, а \(2\) отсутствует).

Помогите Даше найти такой подотрезок, либо скажите, что такого подотрезка не существует.

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

Во второй строке входных данных вам дано \(n\) целых чисел \(a_1, a_2, \ldots a_n\) (\(1 \leqslant a_i \leqslant n\)) — элементы перестановки.

Формат выходных данных
Если искомого подотрезка не существует, выведите \(-1\).

Иначе выведите такие два числа \(l\) и \(r\) \((1 \leqslant l \leqslant r \leqslant n)\), что \([a_l, a_{l + 1}, \ldots, a_r]\) удовлетворяет условиям задачи.

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