Отборочный раунд завершен

Задания

Показывать по одной задаче на странице / все задачи на одной странице

"A" Маленькие числа
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

У мальчика Влада есть два любимых числа a и b. Недавно его в школе научили делить и умножать, и он сразу побежал делить и умножать свои любимые числа.

Сначала он написал в тетрадке числа a и b, после чего решил, что будет последовательно производить с ними одну из трёх операций:

  • Поделить оба числа на какой-то из их общих делителей;
  • Поделить a на один из его делителей g, а b умножить на g;
  • Поделить b на один из его делителей g, а a умножить на g.

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

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

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

Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t (1 ≤ t ≤ 500).

Каждый тест описывается следующим образом: в единственной строке описания теста содержатся два числа a и b (1 ≤ a, b ≤ 109) — любимые числа Влада.

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

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

Если ответов несколько, то разрешается вывести любой из них.

Примеры
Входные данные
2
4 5
4 6
Выходные данные
1 5
2 3
"B" Новая клавиатура
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

Петя купил новую клавиатуру. Она поддерживает n раскладок. В каждой раскладке можно набирать некоторое подмножество строчных букв латинского алфавита. Пронумеруем раскладки от 1 до n.

Петя хочет набрать некоторое сообщение, состоящее из m строчных букв латинского алфавита. Исходно активна первая раскладка. Петя может производить следующие действия:

  • Переключить раскладку. Тогда, если текущая раскладка имела номер i, новая раскладка будет иметь номер i mod n + 1, где mod — операция взятия остатка по модулю. Если предыдущим действием Петя также переключал раскладку, это действие займет b миллисекунд, иначе это действие займет a миллисекунд.
  • Набрать символ. Петя может добавить в конец текущего сообщения любую букву, содержащуюся в текущей раскладке. На это действие он потратит c миллисекунд.

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

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

В первой строке содержатся четыре целых числа n, a, b и c — количество раскладок у клавиатуры, и количество миллисекунд, необходимых для совершения переключения раскладки и набора символа (1 ≤ n ≤ 2 000, 1 ≤ b ≤ a ≤ 109, 1 ≤ c ≤ 109).

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

В последней строке содержится строка s — сообщение, которое хочет набрать Петя (длина строки s от 1 до 2 000). Строка s состоит из строчных латинских букв.

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

Выведите единственное целое число — минимальное количество миллисекунд, необходимое, чтобы набрать сообщение. Выведите  - 1, если набрать сообщение невозможно.

Примеры
Входные данные
5 3 2 1
abc
d
e
f
def
abcdef
Выходные данные
15
Входные данные
1 1 1 1
a
z
Выходные данные
-1
"C" Складывание фигуры
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

Пете как всегда стало скучно на уроке математики, поэтому он стал закрашивать в своей тетради клетки. Когда ему это надоело, он заметил, что у него получилась связная клетчатая фигура из k клеток — между любыми двумя закрашенными клетками существует путь по другим закрашенным клеткам, причем соседние клетки в этом пути имеют общую сторону.

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

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

Рассмотрим второй пример теста из условия. В нем сложенная фигура предславляет собой букву «П», а исходная фигура состоит из 12 клеток. Один из возможных вариантов исходной фигуры представлен на рисунке (сгиб происходит по прямой y = 3):

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

Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t (1 ≤ t ≤ 200).

Каждый из следующих t тестов описывается следующим образом: в первой строке описания теста содержится два целых числа n, k — количество закрашенных клеток, из которых состоит сложенная фигура Васи и количество клеток в исходной фигуре (1 ≤ n < k ≤ 105).

В каждой из следующих n строк содержатся два числа xi, yi — координатылевого нижнего угла i-й закрашенной клетки ( - 108 ≤ xi, yi ≤ 108). Гарантируется, что все закрашенные клетки различны и образуют связную фигуру.

Гарантируется, что сумма k во всех тестах одних входных данных не превосходит 105.

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

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

В первой строке выведите линию сгиба, а в k следующих строках по два целых числа (x'i, y'i) — координаты клеток связной фигуры, которую можно сложить пополам по выведенной линии сгиба, чтобы получить фигуру во входных данных.

Линия сгиба должна быть выведена одним из 4 способов:

  • L num — сгиб производится по прямой x = num, левая часть накладывается поверх правой;
  • R num — сгиб производится по прямой x = num, правая часть накладывается поверх левой;
  • U num — сгиб производится по прямой y = num, верхняя часть накладывается поверх нижней;
  • D num — сгиб производится по прямой y = num, нижняя часть накладывается поверх верхней.

Все x'i, y'i, а также координата линии сгиба по модулю не должны превышать 109. Гарантируется, что такая фигура существует. Если существует несколько подходящих ответов, разрешается вывести любой из них.

Примеры
Входные данные
2
7 14
0 0
0 1
0 2
1 2
2 2
2 1
2 0
7 12
0 0
0 1
0 2
1 2
2 2
2 1
2 0
Выходные данные
L 0
0 0
0 1
0 2
1 2
2 0
2 1
2 2
-1 0
-1 1
-1 2
-2 2
-3 2
-3 1
-3 0
U 3
0 0
0 1
0 2
1 2
2 2
2 1
2 0
0 3
1 3
2 3
0 4
2 4
"D" Остроугольные треугольники
Ограничение по времени 4 секунды
Ограничение по памяти 256 мегабайт

Совсем недавно московский десятиклассник Дмитрий Захаров обогнал всех в построении множества точек в d-мерном пространстве, таких что все треугольники с вершинами в этих точках остроугольные.

Таня решила померяться силами с Дмитрием. Разумеется, она планирует использовать компьютер. Для начала она хочет решить следующую задачу. Дано n точек на плоскости, требуется найти количество остроугольных треугольников с вершинами в этих точках. Треугольник называется остроугольным, если все его углы строго меньше 90 градусов.

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

Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t (1 ≤ t ≤ 666).

Каждый из тестов описывается следующим образом: в первой строке описания теста содержатся число n (3 ≤ n ≤ 2000) — количество точек.

В следующих n строках содержатся по два числа xi, yi ( - 109 ≤ x, y ≤ 109) — координаты точек. Гарантируется, что все точки в одном тесте различные.

Суммарное количество точек по всем тестам одних входных данных не превосходит 2000.

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

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

Примеры
Входные данные
2
5
1 1
2 2
3 3
4 1
6 4
5
0 0
3 1
5 1
5 -1
1 3
Выходные данные
3
4
"E" Объединение массивов
Ограничение по времени 4 секунды
Ограничение по памяти 256 мегабайт

Рассмотрим два массива натуральных чисел A = [a1, a2, ..., an] и B = [b1, b2, ..., bm]. Будем называть их k-объединением лексикографически минимальный массив чисел R длиной k, который разбивается на две непустые подпоследовательности, первая из которых является подпоследовательностью массива A, а вторая — подпоследовательностью массива B.

Формально говоря, необходимо найти лексикографически минимальный массив R = [r1, r2, ..., rk], для которого существуют непустые наборы индексов 1 ≤ i1, 1 < i1, 2 < ... < i1, t ≤ n и 1 < j1, 1 < j1, 2 < ... < j1, k - t ≤ m в исходных массивах, а также наборы индексов 1 ≤ i2, 1 < i2, 2 < ... < i2, t ≤ k и 1 ≤ j2, 1 < j2, 1 < ... < j2, k - t ≤ k, такие что:

  • Для любых 1 ≤ p ≤ t, 1 ≤ q ≤ k - t выполнено i2, p ≠ j2, q;
  • Для любого 1 ≤ p ≤ t выполнено ai1, p = ri1, p;
  • Для любого 1 ≤ p ≤ k - t выполнено bj1, p = rj1, p.

Например, если A = [1, 2, 1, 3, 1, 2, 1], B = [1, 2, 3, 1], а k = 9, то их k-объеднением будет R = [1, 1, 1, 1, 2, 1, 2, 3, 1] (подпоследовательность из первого массива — [1, 1, 1, 2, 1], подпоследовательность из второго массива — [1, 2, 3, 1]).

По двум данным массивам A и B, а также числу k найдите их k-объединение R.

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

В первой строке ввода содержится число n — размер массива A (1 ≤ n ≤ 3000).

Во второй строке содержится n чисел ai — массив A (1 ≤ ai ≤ 3000).

В третьей строке содержится число m — размер массива B (1 ≤ m ≤ 3000).

Во четвертой строке содержится m чисел bi — массив B (1 ≤ bi ≤ 3000).

В последней строке содержится число k (2 ≤ k ≤ n + m).

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

Выведите k-объединение заданных во входном файле массивов.

Примеры
Входные данные
7
1 2 1 3 1 2 1
4
1 2 3 1
9
Выходные данные
1 1 1 1 2 1 2 3 1 
"F" Два поддерева
Ограничение по времени 4 секунды
Ограничение по памяти 256 мегабайт

Рассмотрим подвешенное дерево. Рассмотрим вершину v, имеющую в поддереве хотя бы одну вершину на расстоянии k от v. Будем называть k-поддеревом вершины v дерево, полученное из поддерева вершины v удалением всех вершин, расстояние от которых до v больше k. Например, на иллюстрации ниже красным отмечено 2-поддерево вершины 3.

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

Дано подвешенное дерево. Требуется определить наибольшее k такое, что у него есть два одинаковых k-поддерева, корни которых различны. Эти поддеревья могут пересекаться.

На рисунке приведены деревья из примеров.

В первом примере корни одинаковых 1-поддеревьев — это вершины 2 и 3.

Во втором примере корни одинаковых 3-поддеревьев — это вершины 1 и 4.

В третьем примере корни одинаковых 0-поддеревьев — это вершины 1 и 2.

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

В первой строке задано число t — количество тестов (1 ≤ t ≤ 104).

Каждый из t тестов описывается следующим образом: в первой строке задано число n — количество вершин (2 ≤ n ≤ 105).

Далее следует n строк. В i-й из них задано число cnti — количество детей вершины i, а далее следуют cnti чисел — номера детей вершины i. Вершины нумеруются с единицы. Корнем дерева является вершина 1. Гарантируется, что заданный граф является деревом с корнем в 1.

Сумма n по всем тестам в одних входных данных не превосходит 2·105.

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

Для каждого теста выведите на отдельной строке максимальное k такое, что существует два одинаковых k-поддерева с разными корнями.

Примеры
Входные данные
3
5
2 2 3
1 4
1 5
0
0
8
1 2
2 3 4
0
1 5
2 6 7
0
1 8
0
2
1 2
0
Выходные данные
1
3
0

Отправить решение

Загрузить Максимальный размер - 256 Кб

Вход

ВКонтакте Facebook It.Mail

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.