Лингвистические задачи всех времён и народов

Интерпретатор языка Scheme на JScript от Алексея Яковлева
$$\left\{\begin{array}{lll} k, m, n\in \mathbb N\\ k^{57}+m^{18}=n^{13}\\ \end{array} \right.$$ В этой задаче нам поможет принцип включения-исключения. Обозначим за B число пар протыканий, которые пересекаются, а за С — число троек протыканий, которые пересекаются в одной точке. Тогда число проткнутых кубиков равно $N^3-K+\frac B2-\frac C6$. Найти B можно за $O(N^2)$, а C — за $O(N^3)$ вложенными циклами по массиву протыканий. Наше решение проходит по времени, так как 1503=3375000, а у нас в распоряжении есть по меньшей мере сто миллионов элементарных операций в секунду. $$\vec{AB}$$

Рассмотрим раскладку ЙЦУКЕН. Каждую букву, расположенную на раскладке клавиатуры, будем обозначать парой чисел $(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\le E\le 10^{100}$ — количество рёбер графа. Во второй строке перечисляются титулы графа. В третьей приводится родословная. Длина входного файла не превышает 64 Кб.

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

Выведите "YES" или "NO" в зависимости от ответа на задачу.
Решения, работающие при $1\le E\le 10^3$, будут оцениваться из 60 баллов.

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

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.

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

Пример

Входные данные Выходные данные
7
5 4
2 2
3 9
0 5
1 3
6 6
4 11
YES
2 3 6
0 5 1
1 0 7
5 0 0
2 4 0
1 0 0
3 0 0
Hosted by uCoz