Задача A. Вложение со сгибом ≡

Условие

Из бумаги вырезаны два прямоугольника со сторонами, параллельными осям координат.

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

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

Входные данные содержат четыре целых числа W₁ H₁ W₂ H₂, где W₁ H₁ — ширина и высота первого прямоугольника, W₂ H₂ — ширина и высота второго прямоугольника.

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

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

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

Ограничения

1 < W₁, H₁, W₂, H₂ < 10⁹

Примеры тестов

1 2 1 1

YES

20 20 10 10

NO

Задача B. Репьюниты ≡

Условие

Тимофей с некоторых пор очень любит цифру один (это случилось после одной интересной истории, о которой он никому не рассказывает), поэтому радуется, когда встречает числа, состоящие из одних единиц. Поговорка "один в поле не воин", фильм "Одиннадцать друзей Оушена", локация "Убежище 111" в игре Fallout каждый раз повышают ему настроение. После того, как Тимофей узнал о существовании позиционных систем счисления с натуральными основаниями, отличными от традиционной десятичной, он вдруг понял, что поводов для радости стало еще больше - ведь теперь можно порадоваться и при виде чисел 4, 31 или 273 - они представляются в некоторых системах счисления в виде записи, состоящей из одних единиц (математики называют такие числа репьюнитами)! Действительно, 4 = 11₃, 31 = 11111₂, 273 = 111₁₆.

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

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

В единственной строке записано одно натуральное число n (в десятичной системе счисления).

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

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

Ограничения

1 ≤ n ≤ 10⁹

Система оценки и описание подзадач

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Подзадача 1: 0 ≤ n ≤ 1000, баллы: 30.

Подзадача 2: нет дополнительных ограничений, баллы: 70.

Пояснения к примерам

Комментарий к первому примеру: 31 = 11111₂ = 111₅.

Комментарий ко второму примеру: число 11 представимо в виде репьюнита только в десятичной системе счисления.

Примеры тестов

31

YES

11

NO

Задача C. Мёд и справедливость ≡

Условие

Две пчелы собирают пыльцу с N цветков, расположенных в ряд. Цветок номер i содержит a_i микрограмм пыльцы.

Пчёлы договорились, что первая пчела будет собирать пыльцу с цветков на участке от L до M включительно, а вторая  — от M + 1 до R включительно (L ≤ M < R). Чтобы ни одной из пчёл не было обидно, сумма запасов пыльцы на первом и втором участках пчёл должны совпадать.

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

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

Входные данные содержат целое число N, за которым следует N чисел a_i.

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

Выходные данные должны содержать целые числа L M R — границы участков. Если оптимальных решений несколько, выведите решение с наименьшим значением L. Если решения не существует, выведите единственное число  − 1.

Ограничения

2 ≤ N ≤ 10000

1 ≤ a_i ≤ 10⁵

Примеры тестов

3
1 1 2

1 2 3

2
2 5

-1

Задача A. В ожидании Нового года ≡

Условие

31 декабря. Марфа Геннадьевна и Глафира Сергеевна уже приготовили новогодний ужин, и теперь они с нетерпением ждут Нового года.

Каждые 5-10 минут они смотрят на часы и вычисляют, сколько часов и минут осталось до Нового года. При этом на вычисление у них уходит много времени.

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

Число секунд в текущем времени принять равным 0.

Формат входного файла

Входной файл содержит текущее время — часы и минуты.

Формат выходного файла

Требуется вывести в выходной файл, сколько времени осталось до Нового года — часы и минуты.

Ограничения

Часы от 0 до 23. Минуты от 0 до 59.

Примеры тестов

12 0

12 0

23 59

0 1

22 25

1 35

Задача B. Яблоки поровну ≡

Условие

В школьной столовой на завтрак раздавали яблоки. Каждому школьнику должно было достаться по одному яблоку, но трём из них удалось незаметно набрать в карманы a₁, a₂ и a₃ яблок соответственно.

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

Например, если у первого школьника 2 яблока, у второго — 3, а у третьего — 4, то третий школьник может передать первому одно яблоко, и тогда у каждого из них будет по 3 яблока.

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

Формат входного файла

Входной файл содержит целые числа a₁ a₂ a₃.

Формат выходного файла

Выходной файл должен содержать целые положительные числа x y z — номер школьника, который отдаёт яблоки, номер школьника, которому отдаёт яблоки школьник x, и количество яблок.

Если у школьников уже одинаковое количество яблок, выведите единственное число 0.

Если решения не существует, выведите единственное число  − 1.

Ограничения

1 ≤ a_i ≤ 1000; 1 ≤ x, y ≤ 3

Примеры тестов

3 3 3

0

1 3 5

3 1 2

1 3 6

-1

Задача C. Джордж ≡

Условие

У Джорджа есть текст на английском языке, в котором он упоминается в третьем лице. Джордж решил для ясности заменить в этом тексте все слова he и He на George. При этом слова hE и HE он не заменяет.

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

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

h

h

hehehe he HE

hehehe George HE

Задача D. Слон на шахматной доске ≡

Условие

Слон — шахматная фигура, которая может двигаться на любое число клеток по диагонали.

Имеется шахматная доска N на N клеток. В клетке с координатами (X; Y) находится слон. Требуется вывести шахматную доску с изображением слона и всех клеток, в которые он может походить.

Клетки чёрного цвета обозначаются символом '#' (ASCII 35), клетки белого цвета обозначаются символом '.' (точка, ASCII 46), клетка со слоном обозначается символом 'X' (ASCII 88), клетка, в которую может походить слон обозначается символом '*' (ASCII 42).

Ось ординат (OY) направлена вертикально вниз. Верхний левый угол доски имеет чёрный цвет и координаты (1; 1).

Формат входного файла

Входной файл содержит целые числа N X Y.

Формат выходного файла

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

Ограничения

2 ≤ N ≤ 100

1 ≤ X, Y ≤ N

Примеры тестов

8
3 5

#.#.#.*.
.#.#.*.#
*.#.*.#.
.*.*.#.#
#.X.#.#.
.*.*.#.#
*.#.*.#.
.#.#.*.#

3 1 2

#*#
X#.
#*#

Задача E. Подсчёт баллов за задачу ≡

Условие

В одной из задач итоговой олимпиады летней школы по информатике имеется N тестов. i-ый тест оценивается в a_i баллов. Итоговый балл за задачу — сумма баллов за каждый тест, ответ на который является правильным.

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

Формат входного файла

В первой содержится единственное число N.

Во второй содержатся N чисел — на i-ом месте находятся баллы за i-ый тест.

В файла содержаться N символов '+' (ASCII 43) или '-' (ASCII 45). Если ответ на i-ый тест верный, то i-ый символ — '+', в противном случае — '-'

Формат выходного файла

Выходной файл должен содержать единственное число — количество баллов за задачу.

Ограничения

1 ≤ N ≤ 100

1 ≤ a_i ≤ 100

Примеры тестов

5
1 2 3 5 10 
+-++-

9

6
1 1 3 5 10 25
+-+--+

29

Задача F. Время в пути ≡

Условие

Время отправления и время прибытия поезда задаются в виде Ч М, где Ч - час от 0 до 23, М - минута от 0 до 59. Время в пути задаётся аналогично в формате Ч М, где Ч - количество часов от 0 до 999, а М - количество минут от 0 до 59.

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

Формат входного файла

Формат выходного файла

Примеры тестов

18 25
7 37

2 2

Задача G. Сложение массива чисел ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3
1 2 3

6

Задача H. Слишком вложенные скобки ≡

Условие

Дана правильная последовательность из круглых скобок. Требуется удалить из неё все скобки, находящиеся на глубине вложенности N и более. Например, в последовательности (()((()(())())))(((()))) выделены скобки, вложенные на 3 и более уровней.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

2
()(())

()(())

3
(()((()(())())))(((())))

(()(()))((()))

Задача I. Ребристый параллелепипед ≡

Условие

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

Например, блок размером 2 × 2 × 2 состоит из 8 ячеек и содержит в себе 54 ребра.

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

Формат входного файла

Входной файл содержит два натуральных числа m n.

Формат выходного файла

Выходной файл должен содержать единственное целое число:

1 — если заданный параллелепипед существует;

0 — в противном случае.

Ограничения

0 < m < 2³², 0 < n < 2⁶⁴

Примеры тестов

8 54

1

6 43

0

Задача A. Правильная запись номера ≡

Условие

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

Российский телефонный номер в международном формате выглядит следующим образом: +7␣код_региона␣локальный_номер. В зависимости от длины кода региона существует 4 допустимых варианта записи:

• +7␣123␣123-45-67
• +7␣1234␣12-34-56
• +7␣12345␣1-23-45
• +7␣123456␣12-34

Сотрудник отдела кадров НИИ АСМ просит Вас написать программу, конвертирующую телефонный номер в международный формат.

Формат входного файла

Входной файл содержит единственную строчку с телефонным номером.

Формат выходного файла

Выходной файл должен содержать единственную строчку — телефонный номер в международном формате.

Ограничения

Каждый телефонный номер работника начинается с подстроки +7 после которой следует код региона и локальный номер. Код региона — первый блок подряд идущих цифр после +7. В качестве символов разделителя могут быть использованы пробелы (ASCII 32) и тире (ASCII 45). Код региона может быть также обрамлён круглыми скобками (ASСII 40 и ASСII 41), в этом случае символы разделителя вокруг скобок могут быть опущены.

Суммарное количество цифр в коде региона и локальном номере равно 10. Длина входной строки не превышает 25 символов.

Примеры тестов

+7 (123)456-7-890

+7 123 456-78-90

+7(9876)543 210

+7 9876 54-32-10

+7-31415 92 - 65-3

+7 31415 9-26-53

Задача B. Гвоздики ≡

Условие

Формат входного файла

В первой строке входного файла записано число N — количество гвоздиков (2 ≤ N ≤ 100). В следующей строке записано N чисел  — координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10 000).

Формат выходного файла

В выходной файл нужно вывести единственное число — минимальную суммарную длину всех ниточек.

Ограничения

Примеры тестов

5
4 10 0 12 2

6

Задача C. Арифметическая прогрессия ≡

Условие

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

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

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

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

Напомним что последовательность a₁, a₂, …, a_n называется арифметической прогрессией, если a_i = a_i − 1 + d для всех i от 2 до n и некоторого d. Число d называется разностью арифметической прогрессии.

Формат входного файла

В первой строке входного файла находится целое число n (1 ≤ n ≤ 100 000). В следующей строке находится 2 n целых чисел по модулю не превосходящих 10⁹ — числа, написанные на карточках, перечисленные в произвольном порядке. Гарантируется, что можно выбрать n из них так, чтобы они образовывали арифметическую прогрессию.

Формат выходного файла

В первой строке выходного файла выведите a₁ и d — первый элемент и разность найденной арифметической прогрессии. Если d = 0, число a₁ должно встречаться среди заданных чисел n раз.

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

Примеры тестов

3
8 7 1 5 4 3

1 3

Задача D. Безопасная поездка ≡

Условие

Вам требуется успеть на важную встречу. Сейчас вы находитесь в точке 0, встреча пройдёт в точке с координатой D метров через T секунд. Но есть ещё одна проблема: светофоры.

Начиная с момента 0, светофор с номером i сначала показывает красный свет в течение a_i секунд, затем зелёный в течение b_i секунд, а затем процесс повторяется. В момент смены сигнала считается, что продолжает гореть предыдущий сигнал.

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

Формат входного файла

В первой строке записаны целые числа T, D и N "--- время до встречи, координата места встречи и число светофоров (1 ≤ T ≤ 10⁹, 1 ≤ D ≤ 10⁹, 0 ≤ N ≤ 50).

В следующих N строках записано по три целых числа a_i, b_i, p_i "--- длительность красного и зелёного сигналов i-го светофора и его положение на пути до встречи (1 ≤ a_i, b_i ≤ 10⁹, 1 ≤ p_i ≤ 10⁹). Позиции светофоров не совпадают, в точке D светофора нет.

Формат выходного файла

Выведите единственное целое число "--- минимальную скорость. Абсолютная или относительная погрешность не должна превышать 10^− 5. Если добраться вовремя невозможно, выведите  − 1.0.

Ограничения

Примеры тестов

10 10 1
3 4 3

1.0

12 16 2
2 3 2
3 2 9

1.7500000000000004

12 13 5
1 2 3
2 2 5
3 3 7
1 6 9
3 4 11

1.25

Задача A. Knapsack problem ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3 7
1 5 6

1 0 1

Задача B. Наибольшая общая подпоследовательность ≡

Условие

Найдите наибольшую общую подпоследовательность двух строк.

Формат входного файла

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

Формат выходного файла

Вывести наибольшую общую подпоследовательность. Если решений несколько, вывести любое.

Ограничения

Длина каждой строки не менее 1 и не превосходят 1000.

Примеры тестов

ababaca
acaba

aaba

Problem C. Hall of water life ≡

Statement

The main hall of the Nearsea Institute of Unspecified Underwater Studies has a shape of a long corridor. Along the corridor, there are N aquariums exhibiting various sea creatures. Aquariums are located at distances x₁, …, x_N from the hall entrance (x_i < x_i + 1).

The institute has recently got a new director, who decided that the aquarium maintenance is too costly, and issued an order to remove M (0 ≤ M ≤ N − 2) aquariums.

To minimize the disruption to the looks of the hall, it was decided that:

1. the first and the last aquariums should be left in their places;
2. the maximum distance between the adjacent aquariums must be as small as possible.

Your program must select aquariums for removal in such a way that the above conditions are satisfied.

Input file format

Input file contains integers N M followed by N integers x_i.

Output file format

Output file should contain a single integer — the smallest possible maximum distance.

Constraints

Sample tests

5 2
1 2 3 4 5

2

4 1
10 21 30 40

19

Задача D. Гвоздики ≡

Условие

Формат входного файла

В первой строке входного файла записано число N — количество гвоздиков (2 ≤ N ≤ 100). В следующей строке записано N чисел  — координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10 000).

Формат выходного файла

В выходной файл нужно вывести единственное число — минимальную суммарную длину всех ниточек.

Ограничения

Примеры тестов

5
4 10 0 12 2

6

Задача E. Лестница ≡

Условие

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

Формат входного файла

В первой строке входного файла записано целое число n (1 ⩽ n ⩽ 100). Во второй строке заданы целые числа a₁, a₂, ... , a_n через пробел ( − 10 000 ⩽ a_i ⩽ 10 000) "--- это числа, записанные на ступеньках.

Формат выходного файла

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

Ограничения

Примеры тестов

2
1 2

3

2
2 -1

1

3
-1 2 1

3

Задача A. Поворот отрезка ≡

Условие

Вершины отрезка AB имеют координаты (X_a; Y_a) и (X_b; Y_b).

Требуется найти координаты вершин отрезка A^* B^* (X^*_a; Y^*_a) и (X^*_b; Y^*_b), полученного путём поворота отрезка AB вокруг точки O (X_o; Y_o) на β градусов.

Формат входного файла

Входной файл содержит целые числа X_a, Y_a, X_b, Y_b, X_o, Y_o, β

Формат выходного файла

Выходной файл должен содержать четыре вещественных числа X^*_a, Y^*_a, X^*_b, Y^*_b с точностью 10^− 3.

Ограничения

0 ≤ |X_a|, |Y_a|, |X_b|, |Y_b|, |X_o|, |Y_o| ≤ 10⁵

0 ≤ β  ≤ 360

Примеры тестов

1 1  2 2  0 0  90

-1.000000000 1.000000000 -2.000000000 2.000000000

1 1  2 2
0 0
45

0.000000000 1.414213562 0.000000000 2.828427125

7 5
11 11
9 8
180

11.000000000 11.000000000 7.000000000 5.000000000

Задача B. Пересечение двух прямых ≡

Условие

Прямая a проходит через точки A₁ (a_X1; a_Y1) и A₂ (a_X2; a_Y2). Прямая b проходит через точки B₁ (b_X1; b_Y1) и B₂ (b_X2; b_Y2).

Требуется найти точку пересечения прямых a и b или установить что прямые параллельны.

Формат входного файла

Во входном файле содержаться восемь целых чисел — a_X1, a_Y1, a_X2, a_Y2, b_X1, b_Y1, b_X2, b_Y2

Формат выходного файла

Выходной файл должен содержать:

• Единственное число  − 1, если прямые совпадают;
• Единственное число 0, если прямые параллельны и не имеют общих точек;
• Два вещественных числа X₀, Y₀ — координаты точки пересечения прямых с точностью 10^− 3, если прямые пересекаются в одной точке;

Ограничения

0 ≤ |a_Xk|, |a_Yk|, |b_Xk|, |b_Yk| ≤ 10⁵

A₁ ≠ A₂

B₁ ≠ B₂

Примеры тестов

0 0  2 2  1 1  3 3

-1

0 0  1 1
2 3  5 6

0

1 1
3 5
-1 5
8 -1

2.000000000 3.000000000

Задача C. Поляна Дров ≡

Условие

Маленький мальчик Фермá живет в деревне. Наступают холодные времена, поэтому бабушка попросила мальчика сходить в лес, чтобы собрать дров. В лесу около деревни, в которой живет Ферма, находится волшебная Поляна Дров, на которой всегда лежат дрова, и никогда не кончаются. Естественно, Ферма должен пойти именно туда.

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

• Деревня находится в точке с координатами (0, 1).
• Поляна находится в точке с координатами (1, 0).
• Граница между лесом и полем — горизонтальная прямая y = a, где a — некоторое число (0 ⩽ a ⩽ 1).
• Скорость передвижения по полю составляет V_p, скорость передвижения по лесу — V_f. Вдоль границы можно двигаться как по лесу, так и по полю.

Найдите точку, в которой мальчик Ферма должен войти в лес, чтобы дойти до Поляны Дров как можно быстрее.

Формат входного файла

В первой строке входного файла содержатся два положительных целых числа — V_p и V_f (1 ⩽ V_p, V_f ⩽ 10⁵). Во второй строке содержится единственное вещественное число — координата по оси Oy границы между лесом и полем a (0 ⩽ a ⩽ 1).

Формат выходного файла

В единственной строке выходного файла выведите вещественное число с точностью не менее 8 знаков после запятой — координата по оси Ox точки, в которой мальчик Ферма должен войти в лес.

Ограничения

Примеры тестов

5 3
0.4

0.783310604

5 5
0.5

0.500000000

Задача D. СЛАУ ≡

Условие

Система линейных уравнений, как всем известно, есть множество уравнений.

Ваша задача — решить её.

Формат входного файла

В первой строке входного файла записано целое число n (1 ⩽ n ⩽ 20). В следующих n строках записано по n + 1 целых чисел: a_{i 1}, …, a_in, b_i. Все эти числа не превышают 100 по абсолютному значению.

Формат выходного файла

Первая строка выходного файла должна содержать одно из следующих сообщений: \texttt{impossible} — решений нет \texttt{infinity} — бесконечно много решений \texttt{single} — единственное решение. В этом случае вторая строка должна содержать n чисел x₁, …, x_n, разделенных пробелами. Решение должно быть выведено ровно с тремя знаками после десятичной точки.

Ограничения

Примеры тестов

2
1 1 1
2 2 2

infinity

2
1 2 0
1 2 1

impossible

2
1 2 1
2 1 0

single
-0.333 0.667

Задача A. Фибоначчи ≡

Условие

Необходимо вывести N первых чисел Фибоначчи, начиная с 0.

Формат входного файла

Входной файл содержит одно целое неотрицательное число N.

Формат выходного файла

Выходной файл должен содержать N первых чисел последовательности Фибоначчи.

Ограничения

0 ≤ N ≤ 94

Примеры тестов

2

0 1

Problem B. Square sort ≡

Statement

Input file format

Output file format

Constraints

Sample tests

5 4 3 10 3 1

1 3 3 4 10

Задача D. Количество инверсий последовательнсти ≡

Условие

Пара элементов (A_i, A_j) последовательности A_N называется инверсией, если A_i > A_j и i < j.

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

Формат входного файла

В первой строке входного файла содержится число N — количество элементов последовательности

Последующие N целых чисел задают саму последовательность

Формат выходного файла

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

Ограничения

2 ≤ N ≤ 10⁵

0 ≤ A_i ≤ 10⁹

Примеры тестов

7 1 2 5 9 13 16 20

0

9
1 1 2 3 8 6 1 9 9

5

Задача E. K-ая порядковая статистика ≡

Условие

K-ой порядковой статистикой N-элементной последовательности A_N называется число A_K, которое будет стоять на K-ом месте после упорядочивания элементов этой последовательности по возрастанию.

Последовательность A_N задаётся следующим образом. A₁ = P, A_i = (A_i − 1 ⋅ Q) mod V.

Формат входного файла

Во входном файле содержатся целые числа Q V P N K

Формат выходного файла

В выходном файле должно содержаться единственное число — K-ая порядковая статистика исходной последовательности.

Ограничения

V, Q ≠ 0

0 ≤ Q ⋅ V, Q ⋅ P ≤ 2³¹ − 1

1 ≤ K ≤ N ≤ 4 ⋅ 10⁷

Примеры тестов

343 32767 3 10 7

16478

Задача F. Большой линейный коллайдер ≡

Условие

Группа ученых работает в международной научной лаборатории, которая занимается исследованиями поведения элементарных частиц в установке для экспериментов "Большой линейный коллайдер" (БЛК). Установка БЛК представляет собой прямую, в некоторых точках которой размещаются частицы, которые могут перемещаться вдоль прямой.

В очередном эксперименте в БЛК размещаются n частиц, каждая из которых представляет собой либо отрицательно заряженную частицу — электрон e⁻, либо положительно заряженную частицу — позитрон e⁺. В эксперименте i-я частица исходно размещается в точке с координатой x_i. После начала эксперимента в результате работы БЛК частицы начнут перемещаться в разные стороны вдоль прямой: e⁻ частицы перемещаются по направлению уменьшения координаты, а e⁺ частицы — по направлению увеличения координаты. Абсолютные величины скоростей всех частиц одинаковы и равны 1.

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

Ученые выбрали m различных моментов времени t₁, t₂, ..., t_m, для каждого из которых их интересует, какое количество частиц находится в БЛК непосредственно после каждого из этих моментов времени. Отсчет времени начинается с момента 0, когда частицы приходят в движение. Частицы, исчезнувшие в результате взаимодействия в момент времени t_j, не должны учитываться при подсчете количества частиц для этого момента времени.

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

Формат входного файла

Первая строка входного файла содержит число n — количество частиц. Последующие n строк описывают частицы следующим образом: каждая строка содержит по два целых числа x_i и v_i — координату i-й частицы и ее тип соответственно (x₁ < x₂ < x₃ < ...  < x_n). Частица e⁻ описывается значением v_i =  − 1, а частица e⁺ описывается значением v_i = 1.

Следующая строка содержит целое число m — количество моментов времени, которые выбрали ученые. Последняя строка содержит m целых чисел: t₁,t₂,...,t_m.

Формат выходного файла

Для каждого момента времени во входном файле требуется вывести одно число: количество частиц в БЛК непосредственно после этого момента.

Ограничения

1 ≤ n, m ≤ 200000

 − 10⁹ ≤ x_i, m ≤ 10⁹

0 ≤ t_i ≤ 10⁹

v_i равно  − 1 или 1

Описание подзадач и системы оценивания

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

Получение информации о результатах окончательной проверки

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

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

В приведенном примере в начальный момент в БЛК находятся 4 частицы: частица e⁺ в точке  − 1, частица e⁻ в точке 0, частица e⁺ в точке 1 и частица e⁻ в точке 5.

В момент времени 0.5 первая частица e⁺ и первая частица e⁻ сталкиваются в точке с координатой  − 0.5 и исчезают. В момент времени 1 оставшиеся две частицы находятся в точках с координатами 2 и 4, соответственно. В момент времени 2 они сталкиваются в точке 3 и исчезают. Больше в БЛК частиц нет.

Примеры тестов

4
-1 1
0 -1
1 1
5 -1
4
0 1 2 3

4
2
0
0

Problem A. SST for sparse graph ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 3
1 2 10
2 3 10
3 1 10

20

Задача B. Три пути ≡

Условие

Цапля вилка недавно переехала в Антарктику в государство пингвинов — Пингвинию, и устроилась работать в местную логистическую компанию. Всего в Пингвинии N городов и M дорог, по дорогам можно двигаться в обе стороны. Исторически сложилось, что каждый пингвин посещает ровно три города (возможно проезжая по пути через остальные города). Пингвины не любят однообразие, поэтому одна из самых популярных услуг в логистической компании это прокладка маршрутов между тремя городами a, b, c так чтобы при проезде из a в b, из a в c, и из b в с существовал максимум один город который посещался 3 раза.

Как вы уже могли догадаться Цапля просит вас о помощи, у неё скопилось ровно Q запросов вида a, b, c. И для каждого запроса требуется вывести 3 пути, из a в b, из a в c, и из b в c, так чтобы эти пути удовлетворяли заданным требованиям.

Формат входного файла

Входной файл содержит числа N и M. Далее следует M пар чисел u_i и v_i, означающих что города u_i и v_i соединены дорогой. Далее следует число Q, за которым следует Q попарно различных чисел a_i, b_i, c_i.

Формат выходного файла

Выходной файл должен содержать 3 × Q строк, первое число в строке k_i — количество вершин в пути, далее k_i чисел — номера вершин пути в порядке посещения.

Ограничения

3 ≤ N ≤ 1000, 1 ≤ Q ≤ 1000, 1 ≤ M ≤ N ⋅ (N − 1)2, 1 ≤ u_i, v_i ≤ N, u_i ≠ v_i, 1 ≤ a_i, b_i, c_i ≤ N

Примеры тестов

3 2
1 2
2 3
1
1 2 3

2 1 2
3 1 2 3
2 2 3

4 3
1 2
1 3
1 4
2
3 4 1
1 2 4 

3 3 1 4 
2 3 1 
2 4 1 
2 1 2 
2 1 4 
3 2 1 4 

5 6
2 3
4 5
1 2
1 3
1 4
1 5
2
2 3 4
2 3 5

2 2 3 
3 2 1 4 
4 3 2 1 4 
2 2 3 
4 2 1 4 5 
5 3 2 1 4 5 

Задача C2. Разрезание графа ≡

Условие

Дан неориентированный граф. Над ним в заданном порядке производят операции следующих двух типов:

• cut — разрезать граф, то есть удалить из него ребро;
• ask — проверить, лежат ли две вершины графа в одной компоненте связности.

Известно, что после выполнения всех операций типа cut рёбер в графе не осталось. Найдите результат выполнения каждой из операций типа ask.

Формат входного файла

Первая строка входного файла содержит три целых числа, разделённые пробелами — количество вершин графа n, количество рёбер m и количество операций k (1 ⩽ n ⩽ 50 000, 0 ⩽ m ⩽ 100 000, m ⩽ k ⩽ 150 000).

Следующие m строк задают рёбра графа; i-ая из этих строк содержит два числа u_i и v_i (1 ⩽ u_i,  v_i ⩽ n), разделённые пробелами — номера концов i-го ребра. Вершины нумеруются с единицы; граф не содержит петель и кратных рёбер.

Далее следуют k строк, описывающих операции. Операция типа cut задаётся строкой «cut ~u v» (1 ⩽ u,  v ⩽ n), которая означает, что из графа удаляют ребро между вершинами u и v. Операция типа ask задаётся строкой «ask u v» (1 ⩽ u,  v ⩽ n), которая означает, что необходимо узнать, лежат ли в данный момент вершины u и v в одной компоненте связности. Гарантируется, что каждое ребро графа встретится в операциях типа cut ровно один раз.

Формат выходного файла

Для каждой операции ask во входном файле выведите на отдельной строке слово «YES», если две указанные вершины лежат в одной компоненте связности, и «NO» в противном случае. Порядок ответов должен соответствовать порядку операций ask во входном файле.

Ограничения

Примеры тестов

3 3 7
1 2
2 3
3 1
ask 3 3
cut 1 2
ask 1 2
cut 1 3
ask 2 1
cut 2 3
ask 3 1

YES
YES
NO
NO

Задача D. Ребра добавляются, граф растет ≡

Условие

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

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

На первой строке n — количество вершин, m — количество операций "добавить ребро". Следующие m строк содержат пары чисел от 1 до n — описание добавляемых ребер. 1 ≤ n, m ≤ 300 000.

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

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

Ограничения

Примеры тестов

3 3
1 2
2 3
3 1

110

Задача E. Число комнат в лабиринте ≡

Условие

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

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

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

Формат входного файла

Во входном файле "input.txt" построчно хранится двумерный массив символов, представляющий собой карту лабиринта. Свободные клетки в нем обозначаются пробелами (ASCII 32), в то время как все остальные выступают в качестве непроходимых участков.

Формат выходного файла

Выходной файл "output.txt" должен содержать полученное число комнат.

Ограничения

0 < (n, m) ≤ 5000

Примеры тестов

xxxxxxxxx    xxx xx xxxxxxxxxxxx
xxxxxxxxx    xxx xx xxxxxxxxxxxx
xxxxxxxxx    xxx                
xxxxxxxxx    xxxxxxxxx   xxxxxxx
xxx          xxxxxxxxx   xxxxxxx
xxx   xxx    xxxxxxxxx          
xxx          xxxxxxxxx          
xxxxxx  xxx  xxxxxxxxx   xxxxxxx
xxxxxx  xxx  xxxxxxxxx   xxxxxxx
xxxxxx                   xxxxxxx
xxxxxxxxxxxxx            xxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

1

xxx   xxx       xxxx  0000000000
xxx   xxx   xx  xxxx  0000000000
xxx   xxx   xx                  
xxxxxxxxx   xxxxxxxx  aaa    iii
            xxxxxxxx  aaa       
xxx   xxx   xxaa    aa    000iii
              aa    aa    000iii
iiiiii   aaa  aaaaaaaa    000iii
iiiiii   aaa  aaaaaaaa    000iii
000iii                          
000000   000  00000000    000000
000000   0000000000000    000000

3

Задача F. Ещё одна задача про деревья ≡

Условие

Есть граф из N вершин. Изначально он пустой. Нужно обработать M запросов:

1. добавить ребро из вершины v₁ в вершину v₂, при этом вершины v₁ и v₂ находятся в разных деревьях и вершина v₂ является корнем какого-то дерева.
2. по двум вершинам a и b определить, лежат ли они в одном дереве.

Решение задачи: реализуем СНМ с эвристикой сжатия путей:

int n, m, l[NMAX];

int calc_leader (int v)
{
	if (l[v] != v)
		l[v] = calc_leader (l[v]);
	return l[v];
}

int main()
{
	scanf ("%d%d", & n, &m);
	for (int i = 1; i $\lt$= n; i ++)
		l[i] = i;
	for (int i = 1; i $\lt$= m; i ++)
	{
		int x, y, z;
		scanf ("%d%d%d", &z, &x, &y);
		if (z == 1)
			l[y] = x;
		else
		if (calc_leader (x) == calc_leader (y))
			printf ("YES\n");
		else
			printf ("NO\n");
	}
}

Вам же предстоит сделать тест, на котором это решение будет работать долго. Более точно, нужно сделать тест, на котором количество вызовов функции calc_leader будет не меньше, чем 14Mlog₂M.

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

Входной файл содержит два целых числа N и M (1 ≤ N ≤ 10⁶, 1 ≤ M ≤ 10⁵, M ≤ N).

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

Выведите M строк. i-ая строка должна иметь вид 1 $x$ $y$, если i-ый запрос заключается в добавлении ребра из вершины x в вершину y, или 0 $x$ $y$, если спрашивается, лежат ли вершины x и y в одном дереве.

Ограничения

Примеры тестов

2 2

1 1 2
0 1 2

Задача A. Ближайшее число ≡

Условие

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

Формат входного файла

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

Формат выходного файла

В выходной файл необходимо вывести N целых чисел b_i, таких что b_i является ответом на задачу для числа a_i.

Ограничения

1 ≤ N ≤ 10⁶

|a_i| ≤ 10⁹

Примеры тестов

4 1 2 3 4

2 3 4 4

1
1

1

Задача B. Максимум в скользящем окне ≡

Условие

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

Формат входного файла

Первая строка входного файла содержит целое число n - размер массива. Во второй строке содержится строке n целых чисел a_i - сам массив.

В третьей строке указано число m — количество перемещений. В четвертой строке — m символов 'L' или 'R', разделенных пробелами. 'L' означает, что нужно сдвинуть l вправо, 'R' — что нужно сдвинуть r вправо.

Формат выходного файла

В выходной файл выведите в одну строку ровно m чисел, где i-е число — максимальное значение на отрезке от l до r после выполнения i-й операции.

Ограничения

1 ≤ n ≤ 10⁵

|a_i| ≤ 10⁹

0 ≤ m ≤ 2 n − 2

Примеры тестов

4
-3 -2 -1 0
6
RRRLLL

-2 -1 0 0 0 0

10
1 4 2 3 5 8 6 7 9 10
12
RRLRRRLLLRLL

4 4 4 4 5 8 8 8 8 8 8 6

Problem C. Altitude and visibility ≡

Statement

Consider a sequence of numbers a₁, …, a_N, representing heights. Let's say that element a_i has a visibility radius d if a_i ≥ a_j for all j such that 1 ≤ j ≤ N and |i − j| < d.

You task is to find maximum d_i for every a_i.

Input file format

Input file contains integer N followed by N integers a_i.

Output file format

Output file must contain N integers d_i — maximum visibility for every a_i. If maximum visibility radius for element a_i is unlimited, output d_i = 0.

Constraints

1 ≤ N ≤ 10⁶, 0 ≤ a_i ≤ 10⁹

Sample tests

1
10

0 

6
1 5 2 2 1 4

1 0 1 2 1 4 

Задача D. Мёд и справедливость ≡

Условие

Две пчелы собирают пыльцу с N цветков, расположенных в ряд. Цветок номер i содержит a_i микрограмм пыльцы.

Пчёлы договорились, что первая пчела будет собирать пыльцу с цветков на участке от L до M включительно, а вторая  — от M + 1 до R включительно (L ≤ M < R). Чтобы ни одной из пчёл не было обидно, сумма запасов пыльцы на первом и втором участках пчёл должны совпадать.

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

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

Входные данные содержат целое число N, за которым следует N чисел a_i.

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

Выходные данные должны содержать целые числа L M R — границы участков. Если оптимальных решений несколько, выведите решение с наименьшим значением L. Если решения не существует, выведите единственное число  − 1.

Ограничения

2 ≤ N ≤ 10000

1 ≤ a_i ≤ 10⁵

Примеры тестов

3
1 1 2

1 2 3

2
2 5

-1

Задача E. Слон и куб ≡

Условие

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

На внешние ячейки куба, расположенные с трёх сторон, обозначенных на рисунке цифрами 1, 2 и 3, можно нажимать. В результате нажатия числа в ячейке, на которую нажали и во всех ячейках, находящихся за ней (то есть пересекаемых прямой, проведённой через центр нажатой ячейки перпендикулярно стороне куба), увеличиваются на 1.

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

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

Оси координат расположены, как показано на рисунке. Координаты по каждой оси отсчитываются начиная с 1 в направлении, указанном стрелкой.

Описание нажатия на ячейку состоит из номера стороны куба, на которой она расположена, и двух координат: x и y для стороны 1, y и z для стороны 2, x и z для стороны 3.

Описание запроса Вилки состоит из номера стороны куба, которой параллельна плоскость среза, и координаты: z для стороны 1, x для стороны 2, для y для стороны 3. На рисунке показан срез, параллельный стороне 1 с координатой z = 2.

Формат входного файла

Входной файл содержит целые числа M — размер куба и N — количество описаний, за которыми следует N описаний. Каждое описание начинается с целого числа Q_i.

Если Q_i = 1, то это описание нажатия ячейки, и далее следует целые числа n_i u_i v_i p_i — номер стороны, с которой производится нажатие, первая и вторая координаты ячейки на стороне и количество подряд идущих нажатий данной ячейки.

Если Q_i = 2, то это описание запроса суммы на срезе, и далее следуют целые числа n_i w_i — номер стороны, которой параллельна плоскость среза, и соответствующая координата.

Формат выходного файла

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

Ограничения

1 ≤ w_i, u_i, v_i ≤ M ≤ 10³, 1 ≤ N ≤ 10⁵, 1 ≤ p_i ≤ 10, 1 ≤ Q_i ≤ 2, 1 ≤ n_i ≤ 3.

Примеры тестов

1 2
1 1 1 1 2
2 1 1

2

5 4
1 1 5 5 3
2 2 5
2 1 1
2 3 1

15
3
0

3 11
1 1 1 1 1
1 1 1 2 1
1 1 1 3 1
1 1 2 1 3
1 1 2 2 1
1 1 2 3 1
1 1 3 1 5
1 1 3 2 1
1 1 3 3 1
2 2 2
2 3 1

15
27

Задача F. Распознавание метки ≡

Условие

Приложение дополненной реальности пытается найти на изображении, полученном с камеры телефона, метку, представляющую собой ярко раскрашенный прямоугольник. Благодаря контрастному цвету прямоугольника на этапе предварительной обработки изображение удалось преобразовать в массив из W на H элементов, каждый из которых равен либо '#' (ASCII 35), если он принадлежит прямоугольнику, либо '.' (ASCII 46) в противном случае.

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

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

Формат входного файла

Первая строка входного файла содержит целые числа W H N. Следующие H строк содержат по W символов . и # каждая — изображение после предварительной обработки.

Формат выходного файла

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

Ограничения

1 ≤ W, H ≤ 100, 0 ≤ N ≤ W × H

Описание системы оценивания

Решения работающие для W, H ≤ 20 оцениваются из 50 баллов. Баллы выставляются за каждый успешно пройденный тест.

Примеры тестов

3 3 1
.#.
##.
...

3

2 2 0
#.
.#

0

Задача G. Сумма не без разнообразия ≡

Условие

Задана последовательность целых чисел A₁, A₂, …, A_N. Необходимо выбрать из нее подпоследовательность из подряд стоящих чисел A_i, A_i + 1, …, A_j так, чтобы она содержала не менее K различных чисел, и сумма S = A_i + A_i + 1 + …  + A_j была максимальной.

Формат входного файла

Первая строка ввода содержит целые числа N и K (1 ≤ K ≤ N ≤ 200 000). Вторая строка содержит N целых чисел A₁, A₂, …, A_N (| A_i|  ≤ 1 000 000 000).

Формат выходного файла

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

Ограничения

Примеры тестов

7 3
-99 1 2 -100 3 2 3

-89
2 7

3 2
1 1 1

IMPOSSIBLE

Задача A. Дерево ≡

Условие

Дан неориентированный граф. Проверьте, является ли он деревом.

Формат входного файла

В первой строке входного файла заданы через пробел два целых числа n и m — количество вершин и рёбер в графе, соответственно. В следующих m строках заданы рёбра; i-я из этих строк содержит два целых числа u_i и v_i через пробел — номера концов i-го ребра. Граф не содержит петель и кратных рёбер.

Формат выходного файла

В первой строке выходного файла выведите YES, если граф является деревом, и NO в противном случае.

Ограничения

1 ≤ n ≤ 10⁵

0 ≤ m ≤ 10⁵

1 ≤ u_i, v_i ≤ n

Примеры тестов

3 2
1 2
1 3

YES

3 3
1 2
2 3
3 1

NO

Задача B. Лабиринт ≡

Условие

Лабиринт размером N x N клеток задан массивом символов. Символ '#' обозначеет стену, символ '.' — проход. Передвигаться по лабиринту можно шагами по горизонтали или вертикали, но не по диагонали.

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

Формат входного файла

Первая строка входного файла содержит размер лабиринта N.

Следующие N строк содержат по N символов — описание лабиринта.

Формат выходного файла

Выходной файл должен содержать единственное целое число — длину кратчайшего пути, либо −1, если пути не существует

Ограничения

Примеры тестов

2
.#
..

2

2
.#
#.

-1

Problem C. Dijkstra ≡

Statement

You are to write a program that receives a weighted directed graph and finds distances from source vertex S to all other vertices. Distance from S to some vertex W is the minimal length of path going from S to W. Length of path is the sum of weights of its edges.

Vertices are numbered with integers from 1 to N.

Input file format

Output file format

Constraints

Sample tests

5 3 1
1 2 5
1 3 7
3 4 10

0 5 7 17 -1

Задача D. Водовод на о. Русский ≡

Условие

При строительстве нового кампуса ДВФУ на о. Русском по дну пролива был проложен водовод с материка на остров. К сожалению, после завершения строительства все чертежи были утеряны, а строители разъехались. Чтобы восстановить карту водовода, были проведены гидрографические работы.

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

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

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

Формат входного файла

Первая строка входного файла содержит размеры карты — высоту H и ширину W. Далее следует H строк по W символов в каждой — карта.

Формат выходного файла

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

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

Если водовод восстановить невозможно, выведите единственное слово NO.

Ограничения

2 ≤ H, W ≤ 200

Примеры тестов

4 5
...##
##...
.####
...#.

YES
6  2 1  2 2  3 2  3 3  3 4  3 5 

3 6
#.###.
###.##
......

MULTIPLE
9  1 1  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6

3 6
..###.
###.##
..###.

MULTIPLE
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  3 3  3 4  3 5  2 5  2 6

3 3
...
.##
...

NO

Задача E. Змейка ≡

Условие

Подружки Катя и Надя уже давно играют в игру «Змейка».

Поле для игры представляет собой клетчатый квадрат со стороной n. В каждой клетке квадрата может быть либо зеленая лужайка, либо пень. Изначально в их распоряжении находится змейка длиной 1. За один шаг змейка может перемещаться в одном из 4х направлений: вверх, вниз, вправо и влево. Однако змейка не может ползать по пенькам.

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

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

Формат входного файла

В первой строке входного файла находится число n. В последующих n строках содержится по n символов задающих лабиринт. Лужайке соответствует символ ‘.’, пню – ‘#’, i-ому яблоку цифра i

Формат выходного файла

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

Ограничения

2 ≤ n ≤ 10.

2 ≤ k ≤ 8.

Примеры тестов

3
#3.
1.2
#4#
        

6

3
#43
1.2
#5#
        

-1

Задача F. Бег по коридору ≡

Условие

Школьник Петя собрал собственный цветной дисплей с разрешением 2 пикселя по вертикали и N пикселей по горизонтали. Каждый пиксель определяется координатами (a, b), где a — номер строки от 1 до 2, а b — номер столбца от 1 до N.

На дисплее с таким разрешением уже можно играть и Петя разрабатывает одну из игр — "Бег по коридору". По правилам игры, каждый пиксель может быть либо свободен, либо занят препятствием, либо занят игроком, либо занят эликсиром. Игрок может перемещаться в один из смежных пикселей, не занятых препятствием (смежными называются пиксели, соседствующие либо в строке, либо в столбце).

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

Изначально игрок находится в пикселе с координатами (1, 1). Цель игры — добраться до N-ого столбца, минимизировав конечный уровень усталости.

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

Формат входного файла

В первой строке входного файла содержится число N — горизонтальное разрешение дисплея. Далее следует описание игрового поля — пара строк длиной N каждая. Символ "." (точка) соответствует свободному пикселю, символ "#" (решетка) — занятому препятствием, символ "X" (прописная латинская X) — пикселю с эликсиром.

Гарантируется, что первый символ первой строки равен ".", кроме того, последний символ хотя бы одной из двух строк не равен "#".

Гарантируется, что можно добраться до N-ого столбца.

Формат выходного файла

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

Ограничения

2 ≤ N ≤ 100

Примеры тестов

2
..
.#

1

6
....X.
#XXX..

3

Задача G. Перестройка ≡

Условие

В некоторой стране было ровно N городов и M дорог между ними. При этом в этой стране дорожная система была устроена следующим образом:

• между любыми двумя городами не больше одной дороги;
• никакая дорога не соединяет город с самим собой.

После смены власти новое правительство решило провести ряд реформ, среди которых есть реформа, затрагивающая дорожную систему страны. Эта реформа состоит из двух пунктов:

• разрушить одну из существующих дорог;
• построить новую дорогу, которой раньше не было, не ведущую из города в него же.

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

Теперь правительство задумалось о том, сколько существует способов провести реформу. Помогите ему.

Формат входного файла

Первая строка содержит два целых числа N и M. Следующие M строк содержат два числа a_i, b_i  — номера городов, которые соединяет i-я дорога.

Формат выходного файла

Выведите одно целое число  — количество способов провести реформу.

Ограничения

1 ≤ N ≤ 10⁵

0 ≤ M ≤ 2 ⋅ 10⁵

1 ≤ a_i, b_i ≤ N, a_i ≠ b_i

Задача A. Сумма ≡

Условие

Дан массив из N элементов, нужно научиться находить сумму чисел на отрезке.

Формат входного файла

Первая строка содержит два целых числа N и K — число чисел в массиве и количество запросов. (1 ≤ N ≤ 100 000), (0 ≤ K ≤ 100 000). Следующие K строк содержат запросы

• A i x — присвоить i-му элементу массива значение x (1 ≤ i ≤ n, 0 ≤ x ≤ 10⁹)
• Q l r — найти сумму чисел в массиве на позициях от l до r. (1 ≤ l ≤ r ≤ n)

Формат выходного файла

На каждый запрос вида Q l r нужно вывести единственное число — сумму на отрезке.

Ограничения

Примеры тестов

5 9
A 2 2
A 3 1
A 4 2
Q 1 1
Q 2 2
Q 3 3
Q 4 4
Q 5 5
Q 1 5

0
2
1
2
0
5

Задача B. LCA ≡

Условие

Дано дерево из N вешрин, все некоторым образом пронумерованы, а корень имеет номер 1. Найдите LCA для некоторых пар вершин.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

6
1 3
2 3
3 4
3 5
6 2
1 2
6 5

1
3

Задача C. Сумма+присвоение на отрезке ≡

Условие

Формат входного файла

Первая строка входного файла содержит два целых числа N и K — число чисел в массиве и количество запросов. (1 ≤ N ≤ 100 000), (0 ≤ K ≤ 100 000). Следующие K строк содержат запросы:

• A l r x

   — присвоить элементам массива с позициями от l до r значение x (1 ≤ l ≤ r ≤ N, 0 ≤ x ≤ 10⁹)

• Q l r

   — найти сумму чисел в массиве на позициях от l до r. (1 ≤ l ≤ r ≤ N)

Изначально массив заполнен нулями.

Формат выходного файла

На каждый запрос вида

Q l r

Ограничения

Примеры тестов

5 9
A 2 3 2
A 3 5 1
A 4 5 2
Q 1 3
Q 2 2
Q 3 4
Q 4 5
Q 5 5
Q 1 5

3
2
3
4
2
7

Задача D. RMQ ≡

Условие

• «max l r». Найти максимум в массиве a от l-ой ячейки до r-ой включительно.
• «add l r v». Прибавить значение v к каждой ячейке a[] от l-ой до r-ой включительно.

Формат входного файла

Первая строка содержит два целых числа n и q (1 ≤ n, q ≤ 10⁵) — длина массива и число запросов соответственно.

Вторая строка содержит n целых чисел a₁, …, a_n (|a_i| ≤ 10⁵), задающих соответствующие значения массива.

Следующие q строк содержат запросы.

В зависимости от типа запрос может иметь вид либо «max l r», либо «add l r v».

1 ≤ l ≤ r ≤ n, |v| ≤ 10⁵.

Формат выходного файла

Для каждого запроса вида «max l r» требуется в отдельной строке выдать значение соответствующего максимума.

Ограничения

Примеры тестов

5 3
1 2 3 4 -5
max 1 3
add 1 2 5
max 1 3

3
7

Задача E. Range Variation Query ≡

Условие

В начальный момент времени последовательность a_n задана следующей формулой: a_n = n² mod 12345 + n³ mod 23456.

Требуется много раз отвечать на запросы следующего вида:

• Найти разность между максимальным и минимальным значениями среди элементов a_i, a_i + 1, …, a_j.
• Присвоить элементу a_i значение j.

Формат входного файла

Первая строка входного файла содержит натуральное число k — количество запросов (1 ≤ k ≤ 100 000).

Следующие k строк содержат запросы, по одному на строке. Запрос номер i описывается двумя целыми числами x_i, y_i.

Если x_i > 0, то требуется найти разность между максимальным и минимальным значениями среди элементов a_xi, …, a_yi. При этом 1 ≤ x_i ≤ y_i ≤ 100 000.

Если x_i < 0, то требуется присвоить элементу a_|xi| значение y_i.

В этом случае  − 100 000 ≤ x_i ≤  − 1 и |y_i| ≤ 100 000.

Формат выходного файла

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

Ограничения

Примеры тестов

7
1 3
2 4
-2 -100
1 5
8 9
-3 -101
2 3

34
68
250
234
1

Задача F. Автоматизация склада ≡

Условие

Компания занимается автоматизацией склада. На складе хранятся n видов товаров, пронумерованных от 1 до n, каждый вид товара хранится в своём помещении. Товар вида i хранится в помещении с номером i.

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

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

В начале рабочего дня роботу поступил заказ на выдачу m товаров: a₁, a₂, …, a_m. Робот должен выдать товары именно в этом порядке. Для этого он последовательно выполняет следующие действия: открывает помещение, в котором лежит очередной товар, берет товар, закрывает помещение и выдаёт товар клиенту. После этого робот переходит к выдаче следующего товара.

Исходно электронные карты лежат в отсеке в следующем порядке, от верхней к нижней: b₁, b₂, …, b_n. Для каждого помещения в отсеке лежит ровно одна карта.

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

Требуется написать программу, которая по заданным целым числам n и m, последовательности выдаваемых товаров a₁, a₂, …, a_m и начальному положению карт в отсеке для хранения b₁, b₂, …, b_n определяет, какое минимальное количество действий придется совершить роботу, чтобы открыть все помещения в необходимом порядке. Для каждой вынутой карты необходимо также указать позицию, на которую её необходимо вернуть, чтобы добиться оптимального количества действий.