Задача 1. Кот-проводник ≡

Условие

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

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

В первой строке входного файла содержатся целые числа N M. Во второй строке входного файла содержится список команд кота для Алисы, состоящий из букв l, r, u, d, где u —– вверх, d —– вниз, l —– влево, r —– вправо.

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

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

Ограничения

1 ≤ N, M ≤ 1000

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

4 3
rru

4

3 3
ururuu

1

Задача 2. Древнее сложение ≡

Условие

Цивилизация майя использовала для записи натуральных чисел двадцатиричную систему счисления. Число обозначалось последовательностью двадцатиричных цифр, упорядоченных от старших разрядов к младшим.

Каждая цифра представлялась с помощью трёх символов, имевших значения:

• «ракушка» * — ноль,
• «точка» . — один,
• «черта» | — пять.

• сумма их значений равна значению записываемой цифры,
• количество использованных символов минимально,
• символы «точка» предшествуют символам «черта».

Требуется по двум заданным в записи майя числам определить их сумму и представить в той же записи.

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

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

Символ «ракушка» обозначается '*' (ASCII 42), «точка» — '.' (ASCII 46), «черта» — '|' (ASCII 124). Разряды отделяются друг от друга пробелом (ASCII 32).

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

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

Ограничения

Оба числа не превосходят 10⁹.

Строки во входном файле содержат от 1 до 255 символов.

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

.
..

...

.|
....|

|||

.. | .||
| ..||

.. .|| ...

Задача 3. Неправильное сложение ≡

Условие

Володя написал программу, которая складывает в столбик два числа. К сожалению, он не разобрался, как правильно переносить единицу из одного разряда в следующий. Поэтому программа стала выполняться следующим образом. Сначала она складывает последние цифры обоих чисел и записывает результат, как в случае, если он однозначный, так и в случае, если он двузначный. Затем программа складывает предпоследние цифры обоих чисел и результат сложения приписывает слева к результату предыдущего сложения. Далее процесс повторяется для всех разрядов. Если в одном числе цифр меньше, чем в другом, то программа размещает нули в соответствующих разрядах более короткого числа.

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

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

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

Входной файл содержит целые числа a b c.

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

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

В последующих строках выходного файла необходимо вывести все возможные суммы, которые можно получить, складывая числа a, b и c. Суммы следует выводить по одной на строке, в порядке их возрастания и без лидирующих нулей.

Ограничения

1 ≤ a, b, c ≤ 10⁶

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

30 239 566

YES
7945
71215

643 733 553

NO
18129

Задача 4. Замена скобок: выполнение алгоритма ≡

Условие

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

Рассмотрим следующий алгоритм: на каждом шаге выбирается подстрока скобочной последовательности и все скобки в ней заменяются на противоположные, т.е. все символы '(' в этой подстроке заменяются на ')', а все символы ')' — на '('.

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

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

В первой строке входного файла содержится исходная последовательность.

Во второй строке содержится число N.

В каждой из последующих N строк содержится по два числа l_i r_i, задающих позиции первого и последнего символа подстроки, в которой на i-ом шаге меняются скобки.

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

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

Ограничения

1 ≤ N, L ≤ 10⁵

1 ≤ l_i ≤ r_i ≤ L

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

(((((
1
1 5 

)))))

((())(()
3
1 8
2 6
4 7

)(((()((

Задача A. Пересечение двух прямых ≡

Условие

Прямая a проходит через точки A₁ (a_X1; a_Y1) и A₂ (a_X2; a_Y2). Прямая b проходит через точки B₁ (b_X1; b_Y1) и B₂ (b_X2; b_Y2).

Требуется найти точку пересечения прямых a и b или установить что прямые параллельны.

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

Во входном файле содержаться восемь целых чисел — a_X1, a_Y1, a_X2, a_Y2, b_X1, b_Y1, b_X2, b_Y2

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

Выходной файл должен содержать:

• Единственное число  − 1, если прямые совпадают;
• Единственное число 0, если прямые параллельны и не имеют общих точек;
• Два вещественных числа X₀, Y₀ — координаты точки пересечения прямых с точностью 10^− 3, если прямые пересекаются в одной точке;

Ограничения

0 ≤ |a_Xk|, |a_Yk|, |b_Xk|, |b_Yk| ≤ 10⁵

A₁ ≠ A₂

B₁ ≠ B₂

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

0 0  2 2  1 1  3 3

-1

0 0  1 1
2 3  5 6

0

1 1
3 5
-1 5
8 -1

2.000000000 3.000000000

Задача B. Точка в треугольнике ≡

Условие

Вам даны координаты вершин треугольника лежащего на плоскости, а также координаты точки. Следует определить, лежит ли точка внутри или снаружи треугольника. Гарантируется, что точка не может лежать на границе треугольника.

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

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

Ограничения

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

5 5 0 -2 -2 0 0 0

YES

Задача C. Поездка на Хэллоуин ≡

Условие

Владивостокский программист приглашает коллегу к себе домой в гости на празднование Хэллоуина.

Оба программиста живут за городом. Их дома расположены в точках с координатами (X_A; Y_A) и (X_B; Y_B).

В этом районе есть только одна асфальтированная дорога, представимая в виде отрезка с координатами начала (X_S; Y_S) и конца (X_E; Y_E). Дорога является платной: за любой въезд на дорогу (проезд по произвольному участку дороги или только пересечение — не имеет значения) взимается плата в размере C_R. Остальная местность занята полями, которые (в связи со скорым Хэллоуином) сплошь засажены тыквами. При движении на автомобиле по полю взимается плата в размере C_F за каждый километр пути — ущерб за раздавленные тыквы.

Помогите программисту добраться к другу с минимальными затратами.

Обратите внимание, при сколь угодно малом приближении к дороге плата за въезд на неё не взимается. Смотрите пример №3.

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

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

Ограничения

 − 10³ ≤ X_A, Y_A, X_B, Y_B, X_S, Y_S, X_E, Y_E ≤ 10³

1 ≤ C_F ≤ 10³

1 ≤ C_R ≤ 10⁶

Дома программистов находятся в разных точках и не находятся на дороге

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

1 1 2 2 0 3 3 0 1 1

2.414213562373095

1 5 4 0
-2 -2 10 10
1 2

7.656854249492381

10 10 25 19
15 13 20 16
1 1000000

17.492855684535900

Задача D. Столкновение шариков ≡

Условие

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

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

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

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

Ограничения

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

1
0 0 10 0
50 0 -10 0

2.4

Задача E. Пеленг НЛО ≡

Условие

Два радара, расположенные в точках с координатами (0, 0) и (100, 0), обнаружили неопознанный объект. По таинственной причине, связанной, возможно, с внеземной природой объекта, радары оказались способны определить только направление на объект (пеленг), но не расстояние до объекта. Пеленг измеряется в градусах, против часовой стрелки, начиная от направления "на восток" (т. е. пеленг второго радара относительно первого равен 0°, пеленг первого радара относительно второго — 180°).

Требуется найти координаты НЛО или определить, что это невозможно.

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

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

Ограничения

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

45.1 135.0

49.9127 50.0873

135.0 45.0

0 0

Задача F. Точка Ферма-Торричелли ≡

Условие

Для заданных трёх точек A, B, C найти такую точку O, что AO + BO + CO — минимально.

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

Во входном файле содержатся целые числа X_A Y_A X_B Y_B X_C Y_C — координаты точек A, B, C соответственно.

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

Выходной файл должен содержать два числа X_O Y_O — координаты точки O с точностью до 3-х знаков после запятой.

Ограничения

0 ≤ |X_A|, |Y_A|, |X_B|, |Y_B|, |X_C|, |Y_C| ≤ 10⁵

Никакие две точки не совпадают

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

4 2 0 0 2 2

2 2

-2 -3 1 3 4 -2

1.30120904214632 -0.720188590098661