Задача A. Точка в углу ≡

Условие

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

Будем считать, что точка (x, y) внутри прямоугольника находится в углу, если расстояние от точки до одной из вершин прямоугольника строго меньше, чем до центра прямоугольника.

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

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

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

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

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

Ограничения

−10⁴ ≤ x₁,y₁,x₂,y₂ ≤ 10⁴

min(x₁, x₂) ≤ x ≤ max(x₁, x₂)

min(y₁, y₂) ≤ y ≤ max(y₁, y₂)

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

100 200 300 400 290 210

CORNER

100 200 300 400 200 300

CENTER

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

Условие

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

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

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

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

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

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

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

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

Если некоторые неподготовленные ученики никогда не смогут списать, выведите −1.

Ограничения

1 ≤ N ≤ 10⁹

0 ≤ M ≤ N

0 ≤ K ≤ N − M

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

2 1 0

1

4 1 3

3

11 1 8

5

Задача C. Упрощение XOR ≡

Условие

Дано выражение вида a xor b … xor x. Операндами выражения могут быть только строчные латинские буквы. Операнды могут повторяться. Операнды отделяются от операции ровно одним пробелом.

Единственная использующаяся операция — xor, операция "исключающего или".

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

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

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

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

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

Ограничения

Длина строки s не превосходит 10⁶ символов.

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

a xor a xor b xor a xor c xor b

a xor c

a

a

a xor a

0

Задача D. Юбилейная задача ≡

Условие

Пете и Васе было поручено придумать задачу к 20-му четвертьфиналу ACM ICPC в их городе.

Петя долго думал и придумал следующую задачу: дана строка S, найти наиболее часто встречающуюся подстроку в ней.

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

Напишите программу, решающую предложенную Петей задачу.

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

Входной файл содержит единственную строку S, состоящую из строчных латинских букв.

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

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

Ограничения

1 ≤ |S| ≤ 10⁶

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

aaaa

a

ababab

ab

zxcvasqzx

zx

Задача E. Забор по фен-шую ≡

Условие

Марфа Геннадьевна попросила внука построить новый забор вдоль огорода. Внук выполнил просьбу бабушки и построил забор из N досок, в котором доска с номером i имела высоту a_i сантиметров.

Марфа Геннадьевна недавно прочитала книгу, в которой было написано, что гармоничным является забор, состоящий из чередующихся высоких и низких деревянных досок, то есть должно выполняться либо условие a₁ < a₂ > a₃ < a₄ > …, либо условие a₁ > a₂ < a₃ > a₄ < ….

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

Напишите программу, которая по указанным длинам досок a_i определяет новый набор длин b_i, в котором:

1. a_i ≤ b_i,
2. либо b₁ < b₂ > b₃ < b₄ > …, либо b₁ > b₂ < b₃ > b₄ < …
3. сумма b_i минимальна.

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

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

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

Входной файл должен содержать N целых чисел b_i — новые длины досок. Если существует несколько решений, выведите любое из них.

Ограничения

1 ≤ N ≤ 100; 1 ≤ a_i ≤ 100

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

1
20

20

4
11 10 11 15

11 12 11 15

Задача F. Редактор уровней с грибами ≡

Условие

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

Уровень для игры кодируется прямоугольной таблицей символов из N строк и M столбцов. Свободные ячейки таблицы обозначаются символом '.' (ASCII 46). Ячейки, занятые платформами — символом '#' (ASCII 35). Каждый гриб занимает одну ячейку и обозначается символом '*' (ASCII 42).

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

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

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

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

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

Первая строка входного файла содержит числа N M. Далее следует N строк по M символов в каждой — описание уровня.

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

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

Ограничения

1 ≤ N, M ≤ 20

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

4 11
..**.......
.###.*..###
....##.....
.##........

2

Задача G. Грузоперевозки ≡

Условие

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

В базе данных компании содержатся N городов, пронумерованных от 1 до N, и M односторонних дорог между некоторыми из них. Дорога номер i характеризуется тремя числами u_i v_i l_i — начальным городом, конечным городом и длиной дороги. Гарантируется, что u_i ≠ v_i, и не существует двух разных дорог i, j, для которых u_i = u_j, v_i = v_j.

Страна представляет из себя такое множество из одного или более городов, что:

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

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

Запрос на перевозку определяется парой чисел s_j f_j — номерами города отправления и города назначения j-го груза. Напишите программу, которая для каждого из Q запросов определяет наименьшую возможную стоимость перевозки груза.

В тесте из примера имеется две страны. Одна состоит из городов 1, 2, 3, другая — из городов 4, 5.

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

Входной файл содержит целые числа N M — количество городов и дорог соответственно.

Далее следует M троек целых чисел u_i v_i l_i — начальный город, конечный город и длина i-й дороги.

Далее следует целое число Q, за котором идут Q запросов по два целых числа s_j f_j — город отправления и город назначения j-го груза.

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

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

Ограничения

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

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

2
0
-1
0

Задача H. В поисках Васи ≡

Условие

Мальчик Влад идёт в гости к своему другу Васе, который живёт в доме с N подъездами и M этажами. На каждом этаже каждого подъезда расположено одинаковое количество квартир. Влад помнит номер Васиной квартиры X (квартиры нумеруются с 1), но не помнит ни номер подъезда, ни этаж.

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

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

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

В примере 2 для 1-го и 2-го предположения Вася живёт на 10 этаже 1 подъезда, в то время как для 3-го предположения Вася будет жить на 7 этаже 1 подъезда. Влад может сначала подняться на 7 этаж 1 подъезда для проверки 3-го предположения, а потом подняться на 10 этаж этого же подъезда для проверки предположений 1 и 2.

В примере 3 для 1-го предположения количество квартир в доме будет равно 40, а для 2-го предположения — 60. Ни в том, ни в другом случае в доме не найдётся квартиры с номером 100.

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

Входной файл содержит целые числа N M X K — количество подъездов и этажей в доме Васи, номер его квартиры, количество предположений Влада. Далее следуют K различных целых чисел a_i — предположения Влада о количестве квартир на одном этаже одного подъезда дома Васи.

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

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

Если ни одно предположение Влада не позволяет определить, где живёт Вася, то выведите −1.

Ограничения

1 ≤ N, M ≤ 10⁴; 1 ≤ X ≤ 10⁶; 1 ≤ K ≤ 10⁵; 1 ≤ a_i ≤ 10⁵

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

10 10 100
2
1 10

20

10 10 100
3
10 11 15

10

2 10 100
2
2 3

-1

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

Условие

Слон Пахом любит играть с кубами, и недавно приобрёл интересный куб, состоящий из 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