У Павла были два целых положительных числа a и b. Он нашел их сумму s и наибольший общий делитель g, после чего забыл a и b. Помогите ему восстановить исходные числа.
В единственной строке даны два целых числа s и g (1 ≤ s ≤ 109, 1 ≤ g ≤ 109) — сумма и наибольший общий делитель чисел a и b.
Если Павел ошибся, и таких чисел a и b не существует, выведите одно число - 1.
Иначе выведите два целых положительных числа a и b в одной строке через пробел. Если существует несколько возможных решений, разрешается вывести любое.
6 2
4 2
7 2
-1
Дан строго выпуклый многоугольник. Найдите минимально возможную площадь невырожденного треугольника, вершины которого являются вершинами многоугольника.
В первой строке дано целое число n (3 ≤ n ≤ 200000) — количество вершин многоугольника.
В каждой из следующих n строк даны два целых числа xi и yi ( - 109 ≤ xi, yi ≤ 109) — координаты вершин многоугольника.
Гарантируется, что многоугольник строго выпуклый. Вершины даны в порядке обхода против часовой стрелки.
Известно, что площадь треугольника, вершины которого являются целыми точками на координатной плоскости — либо целое, либо полуцелое число.
Выведите целое число — искомую площадь, умноженную на 2.
4
0 1
3 0
3 3
-1 3
5
3
0 0
1 0
0 1
1
4
-999999991 999999992
-999999993 -999999994
999999995 -999999996
999999997 999999998
3999999948000000156
Рекомендуется все вычисления проводить в целых числах, так как точности чисел с плавающей точкой, скорее всего, не хватит.
Павел разрабатывает игру. Для этого ему очень нужны функции, доступные в сторонней библиотеке, слишком известной, чтобы ее называть. Известно, что функция i впервые появилась в версии ai и просуществовала вплоть до версии bi, а в версии bi + 1 ее уже не было в этой библиотеке.
Библиотека не бесплатная, а Павлу нужны все функции. Какое минимальное количество версий надо приобрести, чтобы можно было пользоваться всеми функциями?
В первой строке дано целое число n (1 ≤ n ≤ 200000) — количество функций.
В каждой из следующих n строк дано два числа ai и bi (1 ≤ ai ≤ bi ≤ 109) — промежуток версий библиотеки, в которых была доступна функция i.
В первой строке выведите целое число k — минимальное количество версий библиотеки, которые нужно приобрести, чтобы можно было пользоваться всеми функциями.
Во второй строке выведите k различных целых чисел — номера версий, которые нужно приобрести.
Если существует несколько возможных ответов, разрешается вывести любой.
5
2 4
1 3
2 3
3 6
4 5
2
3 4
Вы играете в футбольный менеджер. Всего в игре есть n футболистов, из них k футболистов — a1, a2, ..., ak — в данный момент играют за вашу команду. Вы хотите, чтобы в вашей команде играли футболисты b1, b2, ..., bk. Для этого вы можете предлагать другим командам обменять одного из своих игроков на другого игрока.
Для каждой упорядоченной пары различных игроков (x, y) известно, согласится ли команда, управляемая компьютером, обменять вашего игрока x на своего игрока y. Определите, получится ли собрать команду, состоящую из футболистов b1, b2, ..., bk, и если да, выведите порядок обменов, который к этому приведет.
В первой строке даны два целых числа n и k (1 ≤ n ≤ 300, 1 ≤ k ≤ n) — общее количество футболистов в игре и количество футболистов в вашей команде.
Во второй строке даны k различных целых чисел ai (1 ≤ ai ≤ n) — текущий состав вашей команды.
В третьей строке даны k различных целых чисел bi (1 ≤ bi ≤ n) — желаемый состав вашей команды.
В каждой из следующих n строк записано по n символов. Символ в i-й строке и j-м столбце равен «1», если управляемая компьютером команда согласится обменять вашего игрока i на своего игрока j, и «0», если не согласится. Символы на главной диагонали равны нулю.
В первой строке выведите «YES», если получится собрать команду из игроков b1, b2, ..., bk, и «NO», если не получится.
В случае ответа «YES» на второй строке выведите целое число q (0 ≤ q ≤ n·n) — количество обменов, а затем q строк — последовательность обменов. Каждая из этих q строк должна содержать два различных числа xj и yj (1 ≤ xj ≤ n, 1 ≤ yj ≤ n) — номер игрока вашей команды, которого вы хотите обменять, и номер игрока другой команды, на которого вы хотите его обменять. Обратите внимание, что после j-го обмена игрок yj станет игроком вашей команды, а игрок xj перестанет быть игроком вашей команды.
Если существует несколько последовательностей обменов, ведущих к желаемому результату, разрешается вывести любую. Также обратите внимание, что не требуется минимизировать количество обменов, достаточно лишь, чтобы оно не превышало n·n.
5 2
1 2
4 5
00100
00100
00011
00000
00000
YES
4
1 3
3 4
2 3
3 5
3 2
1 2
2 3
000
001
010
NO
Даны две строки s и t одинаковой длины. Требуется определить, можно ли из строки s получить строку t, ровно один раз перевернув в ней некоторую подстроку.
В первой строке записана строка s, а во второй — строка t. Обе строки имеют одинаковую длину от 1 до 200000 и состоят из строчных латинских букв.
Выведите «YES», если можно перевернуть некоторую подстроку строки s так, чтобы s стала равна t, и «NO», если этого сделать нельзя.
abcdefg
abedcfg
YES
abcdefg
abdecfg
NO
Есть дерево из n вершин. Для каждой вершины известен список всех ее потомков (не обязательно непосредственных). Требуется восстановить дерево или сказать, что такого дерева не существует.
В первой строке записано целое число n (1 ≤ n ≤ 1000) — количество вершин в дереве.
В каждой из следующих n строк сначала записано число ci (0 ≤ ci ≤ n) — количество потомков вершины i, а затем ci различных целых чисел aij (1 ≤ aij ≤ n) — номера потомков вершины i.
Если ответа не существует, выведите «NO».
Иначе в первой строке выведите «YES», а затем выведите n - 1 строку, по два числа в каждой — номер родителя и потомка. Пары (родитель, потомок) можно выводить в любом порядке.
5
4 2 3 4 5
3 3 4 5
2 4 5
1 5
0
YES
1 2
2 3
3 4
4 5
5
4 2 3 4 5
3 3 4 5
0
1 5
0
YES
1 2
2 3
2 4
4 5
3
3 2 3 1
3 3 1 2
3 1 2 3
NO
Назовем недопалиндромностью массива b длины k минимальное количество раз, которое надо увеличить некоторые элементы bj на 1, так чтобы массив b в результате стал палиндромом, т.е. b1 = bk, b2 = bk - 1, и т.д.
Дан массив длины n, состоящий из целых чисел. Рассмотрим все его подмассивы длины k, а для каждого из этих подмассивов его недопалиндромность pi. Требуется вычислить сумму всех pi (1 ≤ i ≤ n - k + 1).
В первой строке даны два числа n и k (1 ≤ k ≤ n ≤ 200000) — длина массива и длина подмассивов.
Во второй строке даны n целых чисел ai ( - 108 ≤ ai ≤ 108) — элементы массива.
Выведите единственное целое число — сумму недопалиндромностей всех подмассивов длины k.
3 2
3 1 2
3
5 3
2 3 3 1 4
4
Вы играете в новую RPG. Карта мира в ней представляет собой клетчатое поле размером n × m клеток. Любой игровой персонаж, стоящий в какой-либо клетке, может переместиться из этой клетки в четырех направлениях — в клетку слева, справа, спереди и сзади, но не выходя за карту мира.
В некоторых клетках живут монстры. Если в какой-то момент времени вы находитесь на клетке, до которой какой-либо из монстров может добраться за d шагов или меньше, он тут же прибежит и убьет вас.
Вам требуется добраться живым из одной клетки игрового поля в другую. Определить, можно ли это сделать, и если да, какое минимальное количество шагов для этого потребуется.
В первой строке даны три неотрицательных числа n, m и d (2 ≤ n·m ≤ 200000, 0 ≤ d ≤ 200000) — размеры поля и максимальное расстояние, на котором монстры опасны.
Каждая из n следующих строк состоит из m символов. Эти символы могут быть равны «.», «M», «S» и «F», что означает пустую клетку, клетку с монстром, стартовую клетку и финишную клетку соответственно. Стартовая и финишная клетки — пустые, и они встречаются ровно один раз.
Если можно добраться из стартовой клетки в финишную живым, выведите минимальное количество шагов, которое для этого нужно сделать. Иначе выведите «-1».
5 7 1
S.M...M
.......
.......
M...M..
......F
12
7 6 2
S.....
...M..
......
.....M
......
M.....
.....F
11
7 6 2
S.....
...M..
......
......
.....M
M.....
.....F
-1
4 4 2
M...
.S..
....
...F
-1
Обратите внимание, что монстры могут прибежать и убить вас как на стартовой, так и на финишной клетке.
Жюри задумало полное бинарное дерево с n = 2h - 1 вершинами. Его вершины пронумерованы целыми различными числами от 1 до n, однако вам неизвестно, какие вершины с какими соединены.
Вы можете спрашивать у программы жюри, чему равно расстояние между некоторыми двумя вершинами. Вы должны с помощью не более чем 2.5·h·n таких запросов восстановить структуру дерева.
Это интерактивная задача. Ваша программа должна общаться с программой жюри, используя для этого стандартные потоки ввода и вывода.
В самом начале вашей программе сообщается единственное число n (1 ≤ n ≤ 1023, n + 1 — степень двойки) — количество вершин в дереве.
После этого вы можете сделать не более 2.5·h·n запросов. Чтобы сделать запрос, выведите символ «?» и два целых числа от 1 до n — номера вершин x и y, расстояние между которыми вы хотите узнать. В ответ на такой запрос вам будет сообщено одно целое число — расстояние между вершинами x и y.
Как только вы узнаете полную структуру дерева, выведите символ «!», а затем n целых чисел pi, где pi — это предок вершины i, либо число 0, если вершина i является корнем дерева. После этого ваша программа должна завершиться.
<interactor's output>
? 1 2
<interactor's output>
? 2 3
<interactor's output>
! 2 0 2
3
<solution's output>
1
<solution's output>
1
<solution's output>
Обратите внимание, что каждое выведенное вами сообщение должно завершаться переводом строки. Также после вывода каждого сообщения ваша программа должна очищать потоковый буфер, чтобы выведенная вами информация дошла до программы жюри: например, это делают вызовы «fflush(stdout)» или «cout.flush()» в C++, «System.out.flush()» в Java, «Console.Out.Flush()» в C#, «flush(output)» в Pascal, «sys.stdout.flush()» в Python.
Есть n палочек, i-я из которых имеет длину ai. Леша хочет собрать из них как можно больше параллелограммов одновременно, причем каждая палочка может быть использована не более чем в одном параллелограмме. Какое максимальное количество параллелограммов удастся собрать?
В первой строке дано целое число n (1 ≤ n ≤ 200000) — количество палочек.
Во второй строке даны n чисел ai (1 ≤ ai ≤ 200000) — длины палочек.
Выведите единственное целое число — максимальное количество параллелограммов, которое удастся собрать.
4
1 2 1 2
1
12
1 3 5 7 1 3 5 7 1 3 5 7
2
Студия «Lodka Gaming» занимается рекламой своей новой игры «.C.O.N.T.E.S.T: Unexpected Behaviour». Маркетолог студии планирует последовательно пообщаться с n видеоблогерами (в заданном порядке, начиная с 1-го и заканчивая n-м), предложив им записать видеообзор на игру. Все люди разные, и видеоблогеры — тоже, поэтому i-й видеоблогер будет записывать обзор в двух случаях: либо если ему интересна игра, либо если на нее уже записано не менее ai видеообзоров.
Студия хочет, чтобы в сети появилось не менее m видеообзоров. Геймдизайнер «Lodka Gaming» понимает, что, возможно, сами собой эти видеообзоры не появятся, поэтому он хочет убедить некоторых видеоблогеров, что им на самом деле интересна эта игра. Какое минимальное количество видеоблогеров нужно убедить?
В первой строке даны два целых числа n и m (1 ≤ n ≤ 200000, 1 ≤ m ≤ n) — количество видеоблогеров и требуемое количество видеообзоров.
Во второй строке даны n целых чисел ai (0 ≤ ai ≤ 200000) — минимальное количество видеобзоров, которые должны появиться в сети, чтобы i-й видеоблогер записал обзор в случае, если ему неинтересна игра.
Выведите единственное число — минимальное количество видеоблогеров, которых придётся убедить записать обзор на игру, чтобы в сети появилось не менее m обзоров.
7 4
2 1 3 3 4 2 3
1
7 4
2 1 3 3 4 3 2
2
Дана строка s. Также есть строка p, и вначале она пустая. Вам требуется выполнить q операций вида «добавить букву в конец строки p» и «удалить букву с конца строки p», а после выполнения каждой операции нужно сказать, содержится ли p в s в качестве подпоследовательности.
В первой строке дана строка s, имеющая длину от 1 до 200000 и состоящая из строчных латинских букв.
Во второй строке дано целое число q (1 ≤ q ≤ 200000) — количество операций.
В каждой из следующих q строк дано описание операции в формате «push c», что означает «добавить букву c в конец строки p» (c — строчная латинская буква), или «pop», что означает «удалить букву с конца строки p». Гарантируется, что операция «pop» никогда не применяется к пустой строке p.
Выведите q строк, каждая из которых равна «YES» или «NO», в зависимости от того, содержится ли строка p в строке s в качестве подпоследовательности после выполнения очередной операции.
abcabc
30
push a
pop
push a
push a
push a
pop
push c
push b
pop
pop
push b
push c
push c
pop
pop
pop
pop
push b
push c
push c
pop
push b
push c
pop
pop
push a
push b
push c
push a
pop
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
Три мага пытаются вспомнить заклинание. Каждый из них считает, что это некоторая строка длины n, и известно, что каждый из них ошибается не более чем в одной букве. Требуется восстановить забытое заклинание.
Во входных данных даны три строки одинаковой длины n (1 ≤ n ≤ 200000), состоящие из строчных латинских букв.
Если такая ситуация невозожна, выведите «Impossible».
Если существует несколько заклинаний, удовлетворяющих условию, выведите «Ambiguous».
Наконец, если забытое заклинание единственно возможное, выведите его.
aab
aca
daa
aaa
abc
aca
abc
Ambiguous
abcde
fghij
klmno
Impossible