#114311

Везувий

Темы: [Бор] [Топологическая сортировка]

Члены комиссии соревнования ICPC не смогли придумать задачи, поэтому они решили ранжировать команды лексикографически. Таким образом, победителем станет команда, название которой лексикографически самое маленькое. Героиня этой задачи, Этна, является лидером команды, личность которой мы будем скрывать. Название её команды начинается с буквы «Z», что ставит её в довольно плохое положение. После долгих разговоров с комитетом Этна смогла добиться более справедливого способа ранжирования команд. К сожалению, команды будут продолжать сортировать лексикографически, но определение лексикографического порядка изменится. А именно, комитет случайным образом выберет перестановку букв английского алфавита и определит лексикографический порядок, используя эту перестановку. Этна сразу же достала свой ноутбук и написала программу, которая находит перестановку букв для каждой команды, согласно которой эта команда выиграет соревнование. К сожалению, программа еще не закончена. Помогите Этне и напишите более эффективную программу с той же функциональностью.

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

На первной строке дано натуральное число $N$, которое обозначает количество команд, участвующих в соревновании.

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

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

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

Система оценки

В этой задаче 3 подгруппы. Обозначим $L$ - суммарную длину строк, $K$ - количество различных букв.

(13 баллов) $1 \le N \le 100, 1 \le L \le 10000, 1 \le K \le 6$

(32 балла) $1 \le N \le 350, 1 \le L \le 10000, 1 \le K \le 26$

(55 баллов) $1 \le N \le 25000, 1 \le L \le 1000000, 1 \le K \le 26$

Примеры

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

3
war
zag
wro

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

yxwzvutsqponmlkjihgfedcbar
zyxwvutsrqponmlkjihgfedcba
yxwzvutsrqponmlkjihgfedcba

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

3
b
ab
aa

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

zyxwvutsrqponmlkjihgfedcba
nemoguce
zyxwvutsrqponmlkjihgfedcab

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

7
bcada
dbaab
bbabc
ababb
aacdf
bcdff
baddb

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

zyxwvutsrqponmlkjihgfecbad
zyxwvutsrqponmlkjihgfedcba
zyxwvutsrqponmlkjihgfebdca
nemoguce
zyxwvutsrqponmlkjihgfecadb
zyxwvutsrqponmlkjihgfecbda
nemoguce

#114313

Солнечные панели

Темы: [Корневая эвристика (sqrt декомпозиция)] [Арифметические алгоритмы]

Байтазар планирует заняться производством солнечных панелей. Он получил $n$ заказов, каждый заказ характеризуется минимальной $w_{min}$ и максимальной $w_{max}$ шириной солнечной панели, а также минимальной $l_{min}$ и максимальной $l_{max}$ длиной солнечной панели. Выполняя заказ, Байтзар может изготовить солнечную панель любого размера $a \times b$, такого что $w_{min} \le a \le w_{max}, l_{min} \le b \le l_{max}$. Солнечная панель состоит из квадратных ячеек. Ячейка может иметь любой размер $c \times c$, где $c$ — целое число. Байтазар хотел бы использовать для каждого заказа как можно большие по размеру ячейки. Помогите ему найти для каждого заказа максимальное $c$, такое что он сможет выполнить заказ, используя ячейки $c \times c$.

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

Первая строка ввода содержит число $n$ ($1 \le n \le 1000$) — количество заказов. Следующие $n$ строк содержит по четыре целых числа $w_{min}, w_{max}, l_{min}, l_{max}$ и описывают заказы ($1 \le w_{min} \le w_{max} \le 10^9, 1 \le l_{min} \le l_{max} \le 10^9$ ).

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

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

Система оценки

Подзадача 1 (10 баллов): $1 \le n \le 10$

Подзадача 2 (40 баллов): $1 \le l_{max}, w_{max} \le 10 ^ 7$

Подзадача 3 (50 баллов): Нет дополнительных ограничений. Зависит от подзадач 1 и 2.

Примеры

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

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

#114315

Соответствие наборов

Темы: [Z-функция, Префикс-функция] [Декартово дерево] [Хеш]

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

Логотип состоит из $n$ вертикальных полос различной высоты. Полосы пронумерованы от $1$ до $n$ слева направо. Логотип описывается перестановкой $(s_1, s_2, ..., s_n)$ чисел $1, 2, ..., n$. Полоса с номером $s_1$ - самая низкая, полоса с номером $s_2$ - следующая по высоте и, наконец, полоса $s_n$ - самая высокая. Фактическая высота полос не имеет большого значения. Вдоль главной улицы расположено $m$ зданий. К вашему удивлению, высота зданий различна. Задача состоит в том, чтобы найти все позиции, на которых логотип соответствует зданиям. Помогите компании и найдите все непрерывные последовательности зданий, которые соответствуют логотипу. Непрерывная последовательность зданий соответствует логотипу, если здание $s_1$ в этой последовательности является самым низким, здание $s_2$ является следующим по высоте и т. д. Например, последовательность зданий высотой $5, 10, 4$ соответствует логотипу, описанному перестановкой $(3, 1, 2)$, поскольку здание №3 (высотой 4) является самым низким, здание №1 - вторым по высоте, а здание №2 - самым высоким.

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

Первая строка стандартного ввода содержит два целых числа $n$ и $m$ $(2 \le n \le m \le 1 000 000)$.

Вторая строка содержит $n$ целых чисел $s_i$, образующих перестановку чисел $1, 2, ..., n$. То есть $1 \le s_i \le n$ и s$_i \neq s_j$ для $i \neq j$.

Третья строка содержит $m$ целых чисел $h_i$ - высоты зданий ($1 \le h_i \le 10^9$ для $1 \le i \le m$). Все числа различные.

В каждой строке числа разделены пробелами.

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

Первая строка стандартного вывода должна содержать целое число $k$ – количество совпадений.

Вторая строка должна содержать $k$ целых чисел - индексы зданий начиная с 1, которые соответствуют первой полосе из логотипа в правильном соответствии. Числа должны быть перечислены в возрастающем порядке.

Если $k = 0$, ваша программа должна напечатать пустую вторую строку.

Система оценки

В тестах суммарной стоимостью не менее 35 баллов $n \le 5000$ и $m \le 20 000$.

В тестах суммарной стоимостью не менее 60 баллов $n \le 50 000$ и $m \le 200 000$.

Примеры

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

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

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

2
2 6

#114317

Воздушные шарики

Темы: [Стек] [Элементарная геометрия]

Организаторы CEOI 2011 собираются устроить вечеринку с кучей воздушных шариков. Всего будет $n$ шариков (они все имеют форму идеального шара), и они будут лежать на одной линии на полу.

Шарики ещё не надуты, и каждый из них изначально имеет нулевой радиус. Ещё, $i$-й шар прикреплён к полу в позиции $x_i$. Они будут надуваться последовательно, слева направо. Когда какой-то шарик надувается, его радиус непрерывно увеличивается, пока не достигнет верхней границы своего размера, $r_i$, либо же не каснётся одного из уже надутых. $\text{[math]}$ Картинка 1: Шары из примера, после надувания.

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

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

В первой строке входных данных содержится целое число $n$ ($1\le n\le 200 000$) – количество шаров.

Следующие $n$ описывают шары. $i$-я из них содержит два целых числа $x_i$ и $r_i$ ($0\le x_i\le 10^9$), $1\le r_i\le 10^9$). Последовательность $x_i$ строго возрастает.

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

Выведите $n$ строк, в $i$-й строке должно быть единственное целое число – радиус $i$-го шара после надувания. Ваш ответ будет считаться верным, если он отличается от правильного не больше, чем на 0.001 в каждом числе.

Система оценки

1. (40 баллов) $n\le 2000$.

2. (60 баллов) $n\le 200000$.

Примеры

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

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

9.000
1.000
4.694

#114320

Взлом сейфа

Темы: [Динамика по подмножествам] [Динамическое программирование на поддеревьях] [Дерево отрезков, RSQ, RMQ]

Фермер Джон спрятал ключи от трактора в сейфе. Коровы пытаются взломать этот сейф. Сейф защищён сложной парольной системой.

Она организована как подвешенное за вершину 0 дерево из $n$ ($1 \le n \le 20000$) вершин, каждая из которых требует цифру от $0$ до $9$. Вершины пронумерованы от $0$ до $n - 1$.

Единственная информация, которой владеют коровы – что определённые последовательности длины $5$ не появляютя на путях в этом дереве начиная с каких-то стартовых позиций при движении вверх по дереву.

По заданным $m$ ($0 \le m \le 50000$) последовательностям длины $5$, вместе с их стартовой позицией в дереве помогите коровам вычислить сколько паролей будет не подходить.

Вы должны выводить свой ответ по модулю $1234567$.

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

Первая строка ввода содержит два разделённых пробелом целых числа, $n$ и $m$ ($1 \le n \le 20000, 0 \le m \le 50000$) - количество вершин в дереве и количество запрещённых последовательностей соответственно.

В последующих $i$ строках находится описание дерева. Строка $i + 1$ содержит одно целое число $p[i]$, означающее родителя вершины $i$ в дереве ($0 \le p[i] \lt i$).

В последующих $m$ строках находится описание запрещённых последовательностей. Строка $n + i$ содержит два целых числа $v_i$ и $s_i$, разделенные пробелом - стартовую вершину последовательности, и строку из $5$ цифр, которая не встретится в шифре начиная с вершины $v_i$ если двигаться вверх по дереву ($0 \le v_i \lt n$) соответственно.

Гарантируется, что корень дерева находится не менее чем в 4 шагах от $v_i$.

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

Выведите единственное целое число – количество неподходящих конфигураций цифр по модулю $1234567$.

Система оценки

Подзадача 1 (10 баллов): $1 \le n \le 15, 0 \le m \le 15$

Подзадача 2 (15 баллов): $1 \le n \le 1000, 0 \le m \le 2000$

Подзадача 3 (20 баллов): $1 \le n \le 1000, 0 \le m \le 50000$

Подзадача 4 (55 баллов): $1 \le n \le 20000, 0 \le m \le 50000$

Примеры

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

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