В этой задаче речь пойдет про одного из участников первого отбора олимпиады «Когнитивные технологии» 2023-2024 года. Для анонимности будем звать этого участника именем Ратибор.

Так вот, Ратибор узнал, что в системе All Cups, на которой проходит олимпиада, есть шесть основных вердиктов, которые можно получить за посылку по задаче: OK, WA, PE, RE, ML и TL. Есть еще несколько вспомогательных вердиктов, но они не заинтересовали Ратибора.

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

Помогите Ратибору определить, каких вердиктов ему не хватает для коллекции.

$$$N$$$-факториалом называется число вида $$$1\cdot 2^2 \cdot 3^3 \cdot \ldots \cdot N^N$$$. Другими словами, это произведение всех чисел от $$$1$$$ до $$$N$$$, где каждый множитель возведен в степень, равную самому себе. Будем считать, что $$$N$$$-факториал определен для $$$N \ge 0$$$, а $$$0$$$-факториал равен $$$1$$$.

Вам дано целое положительное число $$$x$$$. Определите, является ли оно суммой двуx $$$N$$$-факториалов?

Например, если $$$x = 112$$$, то оно является суммой $$$3$$$-факториала и $$$2$$$-факториала, так как $$$112 = 108 + 4$$$, и при этом $$$108 = 1^1 \cdot 2^2 \cdot 3^3$$$, а $$$4 = 1^1 \cdot 2^2$$$

В стране Берляндии есть $$$n$$$ городов и $$$m$$$ двунаправленных дорог между ними. Все города пронумерованы от $$$1$$$ до $$$n$$$, и из любого города страны возможно добраться до любого другого. Между любой парой городов есть не более одной дороги, при этом каждая дорога имеет целую положительную длину.

Внутри страны находятся $$$2$$$ княжества, которые хотят разделить территорию между собой. Столица первого княжества находится в городе с номером $$$a$$$, а столица второго — в городе с номером $$$b$$$.

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

Определите, можно ли разделить территорию так, чтобы одновременно выполнялись $$$4$$$ следующих условия:

• если кратчайшее расстояние от некоторого города $$$x$$$ до $$$a$$$ и $$$b$$$ одинаково, то он находится на границе и не принадлежит никакому из княжеств;
• если кратчайшее расстояние от некоторого города $$$x$$$ до $$$а$$$ меньше, чем до $$$b$$$, он принадлежит $$$1$$$-му княжеству;
• если первые $$$2$$$ условия не верны, город $$$x$$$ принадлежит $$$2$$$-му княжеству;
• нельзя пройти из одного княжества в другое, не пересекая граничный город;

Например, пусть $$$n = 7$$$, $$$m = 9$$$, столица первого княжества находится в городе $$$2$$$, а второго — в городе $$$3$$$. Карта Берляндии выглядит как на рисунке ниже:

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

Мальчик Гена решил на выходных устроить поход. Дом Гены расположен в поле. Рядом с домом находится круглое озеро. Радиус окружности озера равен $$$r$$$. Расстояние от центра озера до дома Гены равно $$$b$$$, где $$$b \gt r$$$. Через поле проходит дорога на расстоянии $$$a$$$ от центра озера, где $$$a \gt r$$$. Если через центр озера и дом Гены провести прямую, то окажется, что она параллельна дороге. Схема расположения объектов изображена на рисунке 1.

Карта местности

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

Найдите длину маршрута Гены.

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

Пример некорректного маршрута

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

Пример корректного маршрута

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

Горилла может начать свой путь в любой вершине с номером $$$v$$$ ($$$2 \le v \le n$$$). Изначально её усталость равна $$$1$$$. Когда горилла поднимается по ребру наверх (ближе к корню), её усталость умножается на вес этого ребра.

Горилла имеет выносливость $$$k$$$, поэтому она откажется идти по ребру, после которого её усталость станет строго больше $$$k$$$ и немедленно закончит путешествие. Если такое ребро не встретилось, горилла закончит путешествие в корне.

Назовём продолжительностью путешествия количество рёбер, по которым прошла горилла. Обозначим продолжительность путешествия из вершины $$$v$$$ как $$$d_v$$$.

Помогите горилле узнать числа $$$d_2, d_3, \ldots, d_n$$$. Другими словами, найдите продолжительности путешествия, если горилла будет начинать свой путь из вершины с номером $$$v$$$ ($$$2 \le v \le n$$$).

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

Участники одной из команд составили название, включающее каждое из их имен, и записали его в строку $$$t$$$ длины $$$m$$$. Однако, такое название получилось слишком длинным! Поэтому они хотят сократить его следующим образом:

• выбрать префикс строки $$$t$$$ минимальной длины, который включал бы все их имена без пересечений.

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

Некоторое множество подстрок входит в строку без пересечений, если никакой символ не принадлежит двум подстрокам одновременно. Например, подстроки «a» и «bc» входят в строку «ababc» без пересечений, а подстроки «aba» и «abc» — нет.

Если название команды возможно сократить — выведите длину минимального подходящего префикса.