Задача A. Нечётный N-угольник
Условие
Выпуклый N-угольник P преобразуется в N-угольник Q путём замены
середин сторон исходного многоугольника P на вершины многоугольника Q.
Требуется по выпуклому N-угольнику Q,
заданному координатами вершин, восстановить координаты
вершин исходного N-угольника P.
Формат входного файла
Входной файл содержит
нечётное число вершин
N,
за которым следуют целочисленные координаты
xi yi вершин многоугольника
Q,
перечисленные в порядке обхода по часовой стрелке.
Значения координат находятся в диапазоне от
−20000 до
20000.
Все числа во входном файле целые и разделены произвольным
количеством пробелов и/или символов перевода строки.
Формат выходного файла
В выходном файле должны содержаться координаты вершин
N-угольника
P,
перечисленные в порядке обхода по часовой стрелке.
При этом первая и вторая вершина должны образовывать сторону,
на которой лежит первая вершина
N-угольника
Q.
Ограничения
3 ≤ N ≤ 999.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3
0 0
0 1
1 0
|
1 -1
-1 1
1 1
|
Задача B. Сокращение одночленов
Условие
Одночлен — это выражение, состоящее из однобуквенных переменных с
операциями умножения и возведения в целочисленную степень.
Именами переменных являются малые латинские буквы.
Умножение обозначается символом '*' (ASCII 42),
возведение в степень - символом '^' (ASCII 94).
Показатель степени состоит из одной десятичной цифры от 1 до 9.
Примеры одночленов: t, a*b*c^2, y*d^1*y^9.
Требуется по данным N + M одночленам построить дробь,
равную произведению первых N одночленов, делённому на произведение оставшихся M одночленов.
При этом:
- Числитель и знаменатель дроби должны быть одночленами.
- Переменная не должна встречаться в дроби более одного раза (т. е. дробь необходимо сократить).
- Степени переменных должны быть целыми числами большими или равными 2.
- В числителе и знаменателе переменные должны быть отсортированы по алфавиту.
Формат входного файла
В первой строке входного файла содержатся числа
N и
M, разделённые пробелами.
Следующие
N + M строк содержат по одному одночлену каждая.
Формат выходного файла
В выходном файле должны быть две строки, содержащие соответственно
числитель и знаменатель результата.
Если после сокращения в числителе и/или в знаменателе
не остаётся ни одной переменной, вместо одночлена следует вывести число 1.
Ограничения
3 ≤ N, M ≤ 999. Длина каждой строки не превосходит 100 символов.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
2 1
x*x^7*x
x*y*z
y^2*z
|
x^10
y
|
Задача C. Три клетки
Условие
На клетчатом поле закрашены три клетки.
Требуется закрасить дополнительно наименьшее количество клеток таким образом,
чтобы все закрашенные клетки образовали 4-связную фигуру.
Т. е. из каждой закрашенной клетки можно было бы добраться в любую другую,
двигаясь только по закрашенным клеткам,
соседним друг с другом по вертикали либо по горизонтали.
Формат входного файла
Во входном файле содержатся целые числа x1 y1 x2 y2 x3 y3 —
координаты трёх различных закрашенных клеток,
разделённые пробелами и/или символами перевода строки.
Формат выходного файла
Выходной файл должен содержать единственное число —
наименьшее количество клеток, которые необходимо закрасить.
Ограничения
Числа находятся в диапазоне от 0 до 100.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
1 1 2 2 3 1
|
1
|
| 2 |
0 0 0 1 10 1
|
9
|
Задача E. Шарик в лабиринте
Условие
Юный программист Петя все свободное от написания программ и
приема пищи время посвящает известной карманной игре "Шарик в лабиринте",
суть которой заключается в том,
чтобы провести шарик по пластмассовому лабиринту.
Для этого лабиринт можно наклонять, отчего шарик начинает катиться
по проходу с ускорением g = 9,811м/с2.
Шарик катится строго по прямой параллельно сторонам лабиринта.
На поворотах шарик мгновенно и полностью останавливается.
Лабиринт имеет размер N × N см и высоту 1 см и состоит из клеток —
кубиков 1 × 1 × 1 см.
Каждый такой кубик является либо проходом, либо стенкой.
Ровно один из кубиков помечен как выход из лабиринта.
Требуется определить минимальное время,
за которое шарик можно перекатить из левого верхнего угла лабиринта к выходу.
Примечание
Путь, пройденный равноускоренно движущимся из состояния покоя телом за время t,
равен
gt2/2.
Формат входного файла
В первой строке входного файла задано число
N.
В следующих N строках задано описание лабиринта.
Каждая строка описания состоит из
N цифр от 0 до 2, разделённых пробелами.
Здесь 0 соответствует пустой клетке, 1 — стенке, 2 — выходу.
При этом цифра 2 встречается во всем описании ровно один раз,
а первая цифра первой строки не равна 1.
Формат выходного файла
В выходной файл нужно вывести минимальное время в секундах
с точностью до трёх знаков после запятой или число -1,
если перемещение шарика к выходу невозможно.
Ограничения
1 ≤ N ≤ 10.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3
0 1 1
1 0 1
2 0 0
|
-1
|
| 2 |
4
0 0 0 1
0 0 0 0
0 1 1 0
0 0 0 2
|
0.156
|
Задача F. Слишком вложенные скобки
Условие
Дана правильная последовательность из круглых скобок.
Требуется удалить из неё все скобки, находящиеся на глубине вложенности N и более.
Например, в последовательности (()((()(())())))(((()))) выделены скобки,
вложенные на 3 и более уровней.
Формат входного файла
Первая строка входного файла содержит число
N.
Вторая строка содержит правильную скобочную последовательность
длиной от 2 до 10000 символов.
Формат выходного файла
Выходной файл должен содержать укороченную скобочную последовательность.
Ограничения
1 ≤ N ≤ 5000.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
2
()(())
|
()(())
|
| 2 |
3
(()((()(())())))(((())))
|
(()(()))((()))
|
