Задача A. Amnesia ≡

Условие

Сегодня на уроке математики Тимофей изучал тему "Пропорция". Домашнее задание он записать в тетрадь поленился, понадеявшись на свою память, и вот результат — Тимофей помнит три из четырех членов пропорции, но не помнит, на каких местах они стояли! Еще он уверен, что ответ на задачу (неизвестный элемент пропорции) является натуральным числом. Помогите Тимофею найти все подходящие ответы на это задание.

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

Первая строка входных данных содержит три натуральных числа, записанных через пробел: a, b и c — известные члены пропорции.

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

Выведите через пробел в порядке возрастания натуральные числа — все возможные различные решения пропорции. Если ни одного решения нет — выведите число -1.

Ограничения

1 ≤ a, b, c ≤ 10⁹

Пояснение к примерам

В первом примере можно составить такую пропорцию: 24 = 36.

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

В третьем примере можно составить такие пропорции: 24 = 816, 24 = 48, 12 = 48.

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

2 3 4

6

2 3 5

-1

2 4 8

1 4 16

Задача B. Bouncing pairs ≡

Условие

Пусть имеются две строки A и B, состоящие из цифр и строчных символов латинского алфавита.

Над строкой A определим операцию SWAP(i, i + 1), заключающуюся в перестановке местами символов, находящихся в позициях i и i + 1.

Требуется определить минимальное число таких операций для преобразования строки A к строке B.

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

Во входных данных содержатся две строки: A и B.

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

Выходные данные должны содержать одно число.

Ограничения

Гарантируется, что требуемое преобразование возможно совершить.

Длины строк не превосходят 2 ⋅ 10⁵.

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

abababababab
babababababa

6

abc
bca

2

Задача C. Confections ≡

Условие

Сегодня у Гриши день рождения! Каждый из его n друзей принёс имениннику в подарок коробку любимых конфет. Поскольку Гриша — мальчик не жадный, то все конфеты он вынул из коробок и разложил по n + 1 тарелочкам и поставил их перед каждым гостем (включая себя). Ко всеобщему восторгу, это удалось сделать без остатка. Сразу же после этого с работы вернулась мама и было решено все конфеты разложить уже по n + 2 тарелочкам. Ко всеобщему удивлению, и это деление удалось совершить без остатка.

По известному количеству конфет в одной коробке k, определите возможное число гостей на празднике.

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

Единственная строка входных данных содержит натуральное число k.

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

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

Ограничения

1 ≤ k ≤ 10⁹

Пояснение к примеру

В примере число конфет в одной коробке равно 6.

Если к Грише пришел один гость, то общее число конфет тоже равно 6. Их несложно разложить без остатка поровну и по двум, и по трем тарелочкам.

Если к Грише пришло два гостя, то общее число конфет равно 12. Их несложно разложить без остатка поровну и по трем, и по четырем тарелочкам.

Других подходящих решений нет.

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

6

2
1 2

Задача D. Disordered polygon ≡

Условие

Женя нарисовал на доске правильный n-угольник, подписал его вершины числами по часовой стрелке в порядке возрастания : "1 2 3 ... n". Подошедший Никита переставил в подписи числа местами, стёр все стороны Жениной фигуры и соединил вершины в получившемся новом порядке (в том числе первую и последнюю вершины). Теперь на доске красуется замкнутая ломаная. Сколько пар отрезков ломаной пересекаются?

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

Первая строка входных данных содержит одно число n. Вторая строка содержит n чисел a₁, a₂… a_n — перестановку вершин многоугольника.

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

Выведите одно неотрицательное целое число — ответ на вопрос задачи.

Ограничения

3 ≤ n ≤ 10⁵

Пояснение к примерам

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

4
1 2 3 4

0

4
1 2 4 3

1

5
2 4 5 3 1

2

8
5 6 1 3 4 7 8 2

8

Задача E. Empty rectangles ≡

Условие

Пусть имеется набор из N двумерных точек, заданных своими координатами (X_i, Y_i).

Требуется определить число всех возможных прямоугольников, удовлетворяющих следующим условиям:

• вершины прямоугольника должны принадлежать исходному множеству точек,
  а его стороны должны быть параллельны осям координат;
• среди остальных точек ни одна не должна лежать на границе либо внутри такого прямоугольника;
• прямоугольник должен быть невырожденным (иметь ненулевую площадь).

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

В начале входных данных находится число N,
за которым следует 2 × N целых чисел, задающих координаты точек: X_i, Y_i.

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

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

Ограничения

Никакие две точки исходного набора
не совпадают между собой.

 − 10⁶ ≤ (X_i, Y_i) ≤ 10⁶,

4 ≤ N ≤ 10⁵

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

12
-35 -17
 43  10
 24 -17
-16 -29
 43  54
-35  40
 43 -29
 24  10
-16  54
-35  10
 43 -17
 24  40

3

12
-20 -34
 17  34
-20  40
-10 -20
-43 -17
 19  15
-15  16
  0 -34
-32  19
  0 -12
-13   0
  0  40

0

Задача F. Fast battlepass ≡

Условие

Паулундра играет в многопользовательский шутер Counter-rant. Совсем недавно в игре стартовал новый сезон боевого пропуска в котором можно получить n из m доступных скинов для оружия. Система открытия скинов несколько необычная: игроку даётся n рун в каждую руну нужно вставить два кристалла цвета которых фиксированы, после чего если руна подходит к оружию, то оружие открывается. Руна подходит к оружию, если оружие содержит оба цвета содержащиеся в руне. Каждое оружие содержит в себе ровно C цветов.

Боевой пропуск состоит из k уровней. За каждый уровень боевого пропуска даётся ровно одни кристалл, для каждого уровня награда известна заранее. За достижение уровня i наградой будет кристалл с цветом a_i. Игрок использует кристалы и руны по своему усмотрению. Так как зарабатывать уровни довольно тяжело, Паулундра хочет узнать какое минимальное количество уровней боевого пропуска она должна открыть для того чтоб получить хотя бы p скинов, при условии, что она будет оптимально распределять кристалы и руны.

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

Первая строка входных данных содержит пять чисел m, C, n, p и k. Далее следует m строк содержащих по C чисел c_ij описывающих цвета оружия с номером i. Следующие n строк содержат по два числа a_i1 и a_i2  — описания рун. Последняя строка входного содержит k числе S_i, где S_i цвет кристалла за получения уровня i.

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

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

Ограничения

1 ≤ m ≤ 100

2 ≤ C ≤ 10

1 ≤ n, p ≤ 10

1 ≤ k ≤ 10⁶

1 ≤ a_i1, a_i2, S_i, c_ij ≤ 10⁹

a_i1 ≠ a_i2

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

5 3 5 4 10
1 2 3
2 3 4
3 4 5
3 4 6
5 6 7
2 3
2 3
3 4
4 5
10 9
4 4 5 2 3 2 3 3 10 10

8

1 2 1 1 1
100 100000
1 2
1

-1

3 2 4 1 5
2 1
3 1
8 8
1 2
1 3
3 4
1 2
1 2 3 1 2

2

Задача G. Graphword ≡

Условие

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

На его юбилей Вася решил подарить ему игру, представляющую собой обобщенный вариант кроссворда — "графворд".

В качестве игрового поля в ней выступает некоторый неориентированный граф,
вершинам которого приписаны строчные буквы латинского алфавита.

В процессе разгадывания "графворда" игроку требуется составлять слова, перемещаясь по ребрам такого графа.

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

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

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

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

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

Далее указано число ребер M, за которым следуют сами ребра,
каждое из которых задается индексами своих вершин: a_i, b_i.
Нумерация вершин начинается с нуля.

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

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

Выходные данные должны содержать единственное число.

Ограничения

1 ≤ N ≤ 10⁴, 0 ≤ M ≤ 10⁴, a_i ≠ b_i, 1 ≤ |W| ≤ 10

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

6
a b c a b c

8
0 1
1 2
1 4
4 3
5 0
2 4
4 5
0 4

abba

4

6
a b c a b c

8
0 1
2 3
0 4
3 4
2 1
4 2
0 2
5 4

abc

5

Задача H. Health and light 2 ≡

Условие

В городке M — радостное событие! На единственной улице установят фонарь и откроют аптеку. Помогите градоначальнику установить оптимальное место для размещения этих объектов.

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

У фонаря есть параметр "яркость", выражающий, на каком расстоянии от фонаря светло. Например, при яркости, равной 10, фонарь, установленный в точке x = 25, будет освещать улицу на отрезке от 15 до 35, включая границы.

У аптеки есть параметр "удаленность", выражающий, на каком расстоянии домов от нее, люди, живущие в этих домах, будут её посещать. Например, при удаленности, равной 100, аптека, размещенная в точке x = 25, будет посещаться людьми, живущими в домах с координатами на отрезке от 0 до 125, включая границы (домов с отрицательными координатами нет).

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

Первая строка входного файла содержит три натуральных числа, записанных через пробел: n — количество домов, a — яркость и b — удаленность. Во второй строке через пробел расположены неотрицательные целые числа x_i — координаты очередного дома, отсортированные по возрастанию.

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

Выведите одно неотрицательное целое число — наибольшее суммарное количество домов, освещенных фонарём и доступных для посещения аптеки. И аптека, и фонарь могут быть установлены в точках с координатами домов.

Ограничения

1 ≤ n, a, b ≤ 10⁵

0 ≤ x_i ≤ 10⁹

Пояснение к примеру

В примере дано десять домов, яркость фонаря 15 и удаленность аптеки 20. Фонарь может быть установлен, например, в точке 115 (будет освещено три дома: 100, 110 и 120). Аптеку можно расположить в точке 20, в этом случае посещать её смогут жители первых пяти домов. В сумме получается 8 домов. Большее количество домов, имеющих "доступ" к фонарю или аптеке получить нельзя.

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

10 15 20
0 10 20 30 40 60 70 100 110 120

8

Задача I. Interactive circles ≡

Условие

Данная задача является интерактивной и предполагает взаимодействие с программой жюри путем отправки и приема сообщений определенного вида.

Имеется некоторая двумерная точка, про которую известно, что она находится внутри окружности радиуса 1.0 с центром в начале координат.

При этом допускается отправлять запросы вида "проверить окружность с центром в (x, y) на попадание в нее данной точки".

В первом запросе радиус окружности полагается равным 0.9. При каждом последующем запросе радиус уменьшается на 0.1.

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

Протокол взаимодействия

При каждом запросе в выходной поток (stdout) требуется выводить два числа (x, y), задающие центр окружности.
Не забывайте сбросить буфер потока (flush) после каждого запроса.

В ответ через входной поток (stdin) будет получено целое число:
1 — если окружность содержит в себе загаданную точку; 0 — если не содержит.

Ограничения

Для корректной работы программы, после каждой команды,
отправленной в выходной поток,
следует осуществлять вывод перевода строки и
выполнять сброс буфера (flush).

Задача J. Journey back home ≡

Условие

Студент Василий, вернувшись в родную деревню на каникулы, с размахом отмечает успешно сданную сессию. Он гуляет по единственной улице, схема которой приведена на рисунке. На этой улице a домов (с номерами 1, 3, 5, …, a × 2 − 1) на левой и b домов (с номерами 2, 4, 6, …, b × 2) на правой стороне. Посередине улицы разлилась огромная лужа, поэтому перейти с одной стороны на другую можно только в начале и в конце улицы.

Находясь около очередного дома, Василий, будучи в изменённом состоянии сознания, случайным образом решает, куда ему идти дальше (каждое из двух возможных направлений он выбирает с вероятностью 12). Если он окажется рядом с трактиром (дом номер t), то непременно зайдет в него и продолжит веселиться до утра, а если окажется рядом со своим жилищем (дом номер h), то решит, что это знак судьбы и ему пора заканчивать развлекаться. Какова вероятность того, что Василий доберется до родного дома и завершит свой праздник, если сейчас он стоит около дома с номером n?

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

Первая строка входного файла содержит два натуральных числа, записанных через пробел: a и b — описание улицы. Вторая строка входного файла содержит три натуральных числа t, h и n, записанных через пробел — описание домов. Гарантируется непротиворечивость входных данных. Гарантируется, что числа t, h и n различны.

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

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

Ограничения

1 ≤ a, b ≤ 10⁹

1 ≤ t ≤ a × 2 − 1, если t — нечётное.

2 ≤ t ≤ b × 2, если t — чётное.

Для h и n ограничения аналогичны t.

Пояснение к примеру

Смотри рисунок. В примере на улице всего три дома (с номерами 1, 2 и 3). На левой стороне дома под номерами 1 и 3, на правой только 2. В данном примере от каждого дома можно пройти к любому другому. Василий с равной вероятностью 12 может попасть как домой, так и в трактир.

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

2 1
1 2 3

1 2

Задача K. Keep on doing! ≡

Условие

На доске записано выражение n − (n − 1) − (n − 2) − (n − 3) − ...  − 3 − 2 − 1 (например, при n = 5 будет написано 5 − 4 − 3 − 2 − 1). Чтобы избежать двойки по математике, Гавриле требуется поставить в этом выражении левую и правую скобки, так, чтобы в результате получился ноль. Сколько у него есть способов это сделать?

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

Входные данные содержат натуральное число n.

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

Выведите в первой строке неотрицательное целое число m — количество способов расставить скобки требуемым образом. В следующих m строках через пробел выведите два натуральных числа a и b — положение скобок (числа от a до b включительно окажутся внутри скобок). Числа a и b выводите в порядке убывания, а пары чисел выводите в порядке убывания a.

Ограничения

4 ≤ n ≤ 10⁵

Пояснение к примерам

В первом примере дано n = 5. К сожалению, у Гаврилы ничего не выйдет, для данного n нет возможности расставить скобки требуемым образом.

Во втором примере дано n = 7. Если все числа от 5 до 3 заключить в скобки, то получится выражение с нужным значением: 7 − 6 − (5 − 4 − 3) − 2 − 1 = 1 − ( − 2) − 3 = 0.

В третьем примере для n = 12 есть несколько способов решить задачу.

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

5

0

7

1
5 3

12

2
11 8
8 2