Рассмотрим раскладку ЙЦУКЕН. Каждую букву, расположенную на раскладке клавиатуры, будем обозначать парой чисел $(n, m)$, где $n$ — ряд клавиш, $m$ — номер клавиши в ряду, считая слева направо. Например, «ш» обозначим за (1, 8), «ы» — за (2, 2), «ю» — за (3, 9).
Определение 1. Межбуквенным расстоянием Павленко $r\,(a, b)$ между клавишами $a = (i,\,j)$ и $b = (k, l)$ называется целое неотрицательное число $|k - i| + |l - j|$.
Определение 2. Межсловным расстоянием Павленко между словами $s$ и $t$ одинаковой длины $k$ называется величина $\sum_{i=1}^k r\,(s_i, t_i)$.

Задача А. Граф.

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

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

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

Задачи по теории чисел
Результаты
Список тем для рефератов

1.1. Нахождение локального минимума. Метода псевдоградиентного спуска.

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

Рассмотрим какую-нибудь функцию, значения которой мы умеем вычислять. Например, $F(x,y)=\sin \left(\frac 12x^2-\frac 14y^2+3\right)\cos(2x+1-e^y)$. Вычислять значения этой функции мы можем с лёгкостью, но вот поискать её точки минимума с помощью учебника математики и ручки с бумагой -- задача уже неразрешимая для обычного школьника. А задача перед нами стоит следующая: найти какой-нибудь из локальных минимумов этой функции с некоторой точностью $\vareps$.

Тогда мы можем действовать по следующему алгоритму:
1. Выбираем начальное решение, радиус окрестности, в которой будет производится поиск нового решения, минимальный радиус, количество итераций, которое алгоритм будет работать без уменьшения радиуса окрестности и улучшения решения и коэффициент, отвечающий за уменьшение радиуса (в нашем случае можно выбрать $x=0,y=0,r=1,r_{min}=10^{-3},baditers=10,\alpha=0.9$).
2. Выбираем новое решение. В нашем случае генерируем случайное направление $\varphi\in[0;2\pi)$ и проходим расстояние $r$ в направлении: $x'=x+r\cos\varphi,y'=y+r\sin\varphi$.
3. Если $F(x',y')\lt F(x,y)$, то «переходим на новое решение» ($x=x',y=y'$) и возвращаемся к шагу 2.
4. Если проработали уже $baditers$ итераций, а решение не улучшилось, то уменьшаем радиус поиска нового решения: $r=\alpha r$.
5. Если $r\lt r_{min}$, то завершаем работу и возвращаем $(x,y)$ в качестве результата.

Этот алгоритм уже будет приемлимо решать большое количество задач. Например, если мы хотим найти какой-нибудь корень уравнения $f(x)=x^3-4x+17\sin x-e^{\frac x2}$, то поиск минимума следует производить по функции $F(x)=|f(x)|$, а на шаге 2 алгоритма выбирать новое решение как $x'=x\pm r$. Разумеется, эту задачу можно решить и без всякого метода псевдоградиентного спуска: сначала можно построить график (или другим шаманством найти отрезок, на котором есть ровно один корень), а затем уточнить этот корень бинарным поиском.

Подытожим: в первом примере множеством решений было множество $\mathbb R^2$ (множество всех пар действительных чисел), во втором -- множество $\mathbb R$. В обоих случаях наши функции были «хорошими» -- они были непрерывными, гладкими и покладистыми. В дальнейшем нам придётся иметь дело с функциями более шероховатым, но такими, которые, как интуитивно кажется, обладают следующим свойством: у каждого решения $m$ из множества $M$ есть окрестность, в пределах которой значения функции меняются несильно. На других функциях ни метод псевдоградиентного спуска, ни метод отжига без дополнительных шаманств работать не смогут.

Настоящий метод градиентного спуска выбирает новое решение в направлении, которое задаётся антиградиентом функции. Что такое антиградиент, я не знаю, но судя по всему, это какая-то математическая прелесть, которая позволяет по решению быстро понимать, в какой стороне от него лежит локальный минимум. Ограничение по времени: 2 секунды Ограничение по памяти: 64 мегабайта

Вам даны пары чисел $(a_i, b_i)$, Вам необходимо построить декартово дерево, такое что $i$-ая вершина имеет ключи $(a_i, b_i)$, вершины с ключом $a_i$ образуют бинарное дерево поиска, а вершины с ключом $b_i$ образуют кучу.

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

В первой строке записано число $N$ — количество пар. Далее следует $N$ ($1 \le N \le 50\,000$) пар $(a_i, b_i)$. Для всех пар $\lvert a_i\rvert, \lvert b_i \rvert \le 30\,000$. $a_i \ne a_j$ и $b_i \neq b_j$ для всех $i \ne j$.

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

Если декартово дерево с таким набором ключей построить возможно, выведите в первой строке YES, в противном случае выведите NO. В случае ответа YES, выведите $N$ строк, каждая из которых должна описывать вершину. Описание вершины состоит из трёх чисел: номер предка, номер левого сына и номер правого сына. Если у вершины отсутствует предок или какой-либо из сыновей, то выводите на его месте число 0.

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

Пример