Пират Джон Сильвер нашел карту, на которой изображен ровно один остров. Карта представляет собой кусок материи, разбитый на клетки: n клеток по вертикали и m клеток по горизонтали. Джон Сильвер знает, что каждая клетка карты обозначает либо сушу, либо воду, однако некоторые из клеток стерлись, и теперь совершенно невозможно разобрать, что же на этих клетках было нарисовано.
Помогите Джону Сильверу восстановить карту острова. Островом называется непустое связное в четырех направлениях (вверх, вниз, влево и вправо) множество клеток суши.
В первой строке записаны два целых числа n и m (1 ≤ n, m ≤ 50) — размеры карты.
Каждая из следующих n строк содержит m символов и описывает карту. Символ равен «#», если клетка обозначает воду, «.», если эта клетка соответствует суше, и «?», если эта клетка стерлась.
Гарантируется, что входные данные содержат хотя бы один символ «.» и хотя бы один символ «?».
Если карту нельзя восстановить так, чтобы на ней оказался изображен ровно один остров, выведите «Impossible».
Если карту можно восстановить единственным образом, выведите n строк по m символов в том же формате, что и во входных данных, заменяя символы «?» на «.» или «#».
Если же карту можно восстановить несколькими способами, выведите «Ambiguous».
5 7
#######
#..#..#
#..?..#
#..#..#
#######
#######
#..#..#
#.....#
#..#..#
#######
5 7
#######
#...#.#
#.?.?.#
#.#...#
#######
Ambiguous
5 7
#######
#.#.#.#
#.#?#.#
#.#.#.#
#######
Impossible
Перестановкой из n чисел называется последовательность целых чисел от 1 до n, где каждое число встречается ровно один раз. Если в перестановке p1, p2, ..., pn для какого либо i верно, что pi = i, то i называют неподвижной точкой перестановки.
Беспорядком называется перестановка без неподвижных точек.
Определим операцию swap(a, b) как обмен местами элементов на позициях a и b.
Для заданной перестановки вычислите наименьшее количество операций swap, с помощью которых можно превратить ее в беспорядок.
В первой строке записано целое число n (2 ≤ n ≤ 200000) — количество элементов в перестановке.
Во второй строке записаны элементы перестановки — n различных целых чисел от 1 до n.
В первой строке выведите целое число k — минимальное количество операций swap, необходимых для образования беспорядка.
В каждой из следующих k строк выведите по два целых числа ai и bi (1 ≤ ai, bi ≤ n) — аргументы очередной операции swap.
Если существует несколько вариантов решения, выведите любой.
6
6 2 4 3 5 1
1
2 5
Есть набор из n отрезков, заданных своей длиной. Найдите отрезок целочисленной длины, который образует невырожденный треугольник с двумя любыми отрезками из набора, или сообщите, что такого отрезка не существует.
Первая строка содержит единственное целое число n (2 ≤ n ≤ 200000) — количество отрезков в наборе.
Вторая строка содержит n целых чисел li через пробел (1 ≤ li ≤ 109) — длины отрезков в наборе.
Если искомый отрезок существует, в первой строке выведите «YES» (без кавычек). В этом случае во второй строке выведите единственное целое число x — длину искомого отрезка. Если существует несколько таких отрезков, выведите длину любого из них.
Если искомого отрезка не существует, в единственной строке выведите «NO» без кавычек.
2
3 4
YES
2
3
3 4 8
YES
6
3
3 4 9
NO
В одномерной стране есть n городов, i-й из которых расположен в точке xi и имеет население pi, причем как все xi, так и все pi попарно различны. Когда в одномерной стране появился интернет, было принято решение поставить главный сервер в самом крупном городе, а из каждого другого города j провести кабель в ближайший к нему город k, такой, что город k крупнее города j (в случае, если таких городов несколько, следовало выбрать более крупный). В этом случае город k назывался предком города j.
К сожалению, министерство связи одномерной страны слишком долго определяет, откуда и куда надо проводить кабели, а население страдает. Поэтому эту задачу придется решить вам. Определите для каждого города, какой город является его предком.
В первой строке содержится единственное целое число n (1 ≤ n ≤ 200000) — количество городов.
Каждая из следующих n строк содержит два целых числа через пробел xi и pi (1 ≤ xi, pi ≤ 109) — координата и население i-го города соответственно.
Выведите n целых чисел через пробел. i-е число должно быть равно номеру города, который является предком i-го города, или - 1, если у i-го города нет предка. Города нумеруются с единицы в порядке упоминания во входных данных.
4
1 1000
7 10
9 1
12 100
-1 4 2 1
3
1 100
2 1
3 10
-1 1 1
3
1 10
3 100
2 1
2 -1 2
Павел создал лучшую игру в мире —«Деление пополам». В этой игре игроку дано квадратное клеточное поле размера n × n. Некоторые из клеток поля помечены и образуют фигуру. От игрока требуется покрасить каждую из клеток этой фигуры в один из двух цветов так, чтобы получившиеся фигуры обоих цветов были бы равны. Фигуры называются равными, если одну из них можно совместить с другой посредством параллельных переносов, отражений относительно горизонтальных и вертикальных осей и поворотов на углы, кратные 90 градусам.
Павел придумал еще один уровень для этой игры, но никак не может понять, имеет ли он решение. Вам предстоит это выяснить.
В первой строке записано целое число n (1 ≤ n ≤ 50) — размер поля.
В каждой из следующих n строк записано по n символов. Символ «.» означает, что клетка не принадлежит фигуре, а «#» — что принадлежит.
Гарантируется, что во входных данных присутствует четное положительное количество символов «#».
Если решения не существует, выведите «NO» (без кавычек).
Иначе выведите «YES» (без кавычек), а затем n строк по n символов, описывающих раскраску клеток фигуры. Символы «.» из входных данных оставьте без изменения, а символы «#» замените на «A» или «B», в зависимости от того, в какой цвет надо покрасить данную клетку.
Если существует несколько решений, выведите любое.
3
{.##}
{###}
{###}
YES
.AA
BAB
BBA
3
{###}
{.##}
{###}
NO
На плоскости есть две материальные точки (x1, y1) и (x2, y2). Они движутся со скоростями (vx1, vy1) и (vx2, vy2) соответственно. Найдите, на каком минимальном расстоянии друг от друга они смогут когда-либо оказаться.
Первая строка содержит четыре целых числа через пробел x1, y1, x2, y2 ( - 104 ≤ x1, y1, x2, y2 ≤ 104) — координаты материальных точек.
Вторая строка содержит четыре целых числа через пробел vx1, vy1, vx2, vy2 ( - 104 ≤ vx1, vy1, vx2, vy2 ≤ 104) — скорости материальных точек.
Выведите единственное действительное число d — минимально возможное расстояние между точками. Абсолютная или относительная погрешность ответа должна быть меньше 10 - 6.
1 1 2 2
0 0 -1 0
1.000000000000000
1 1 2 2
0 0 1 0
1.414213562373095
Леша делает ремонт на даче. У него есть прямоугольный лист железа размером a × b. Ему надо вырезать из него два прямоугольника размерами a1 × b1 и a2 × b2 соответственно. Все разрезы должны быть параллельны сторонам исходного листа. Определите, сможет ли он это сделать.
Первая строка содержит два целых числа через пробел a и b (1 ≤ a, b ≤ 109) — размеры исходного листа.
Вторая строка содержит два целых числа через пробел a1 и b1 (1 ≤ a1, b1 ≤ 109) — размеры первого прямоугольника, который нужно вырезать из исходного листа.
Третья строка содержит два целых числа через пробел a2 и b2 (1 ≤ a2, b2 ≤ 109) — размеры второго прямоугольника, который нужно вырезать из исходного листа.
Выведите «YES», если из исходного листа можно вырезать два описанных в условии прямоугольника, или «NO», если это сделать невозможно. Кавычки выводить не нужно.
12 20
14 7
5 6
YES
12 20
11 9
20 7
NO
Павел собирает друзей на тусовку и хочет, чтобы на ней присутствовало ровно k человек.
Всего у Павла n друзей, и он уже решил, в каком порядке он будет им звонить и приглашать на тусовку. Когда Павел звонит i-му другу, тот сообщает ему, что готов прийти, если всего в тусовке будет участвовать от ai до bi человек.
Как только набирается нужное количество людей, Павел сообщает им об этом, и все организовывается. При этом он не звонит оставшимся друзьям.
Для каждого значения k = 1, ..., n найдите, скольким людям позвонит Павел.
В первой строке записано целое число n (1 ≤ n ≤ 200000) — количество друзей Павла.
В каждой из следующих n строк записано по два целых числа ai и bi (1 ≤ ai ≤ bi ≤ n) — нижняя и верхняя границы количества участников тусовки, при которых i-й друг Павла согласится в ней участвовать.
Данные перечислены в том порядке, в котором Павел будет их узнавать.
Выведите n чисел через пробел. k-е число должно быть равно количеству друзей, которым позвонит Павел, если он хочет, чтобы на тусовке собралось ровно k человек. Если для какого-то k тусовку устроить вообще не получится, выведите для этого k число - 1.
6
3 3
1 2
3 6
3 4
1 4
4 6
2 5 4 6 -1 -1
3
3 3
1 3
3 3
2 -1 3
Леша работает на работе, и сейчас у него тяжелые времена. Ему необходимо выполнить n задач. Для i-й задачи известны крайний срок di, когда эта задача должна быть выполнена (отсчитывая от начального момента времени 0), время ci, необходимое для ее выполнения, а также задачи, которые надо выполнить перед i-й, чтобы можно было начать ее делать. Будем говорить, что i-я задача зависит от этих задач.
В каком порядке Леша должен выполнять задачи, чтобы не просрочить ни одну из них?
Первая строка содержит единственное целое число n (1 ≤ n ≤ 200000) — количество задач.
Следующие n строк описывают задачи. i-я строка начинается с трех чисел di, ci и ri через пробел (1 ≤ di, ci ≤ 109, 0 ≤ ri ≤ n - 1) — крайний срок, к которому должна быть выполнена i-я задача, время, необходимое для ее выполнения, и количество задач, от которых зависит i-я задача, соответственно. Далее в этой же строке через пробел записаны ri чисел — номера этих задач. Гарантируется, что среди этих ri чисел нет числа i.
Задачи нумеруются с единицы в порядке упоминания во входных данных. Сумма всех ri во входных данных не превышает 200000.
В первой строке выведите «YES» (без кавычек), если Леше удастся выполнить все задачи, не превысив ни один из крайних сроков, или «NO» (без кавычек) в противном случае.
Если ответ «YES», во второй строке выведите n чисел через пробел — номера задач в том порядке, в котором их следует выполнять, чтобы уложиться во все крайние сроки. Если существует несколько подходящих ответов, выведите любой из них.
3
10 5 0
2 2 0
5 3 0
YES
2 3 1
2
100 1 0
10 10 1 1
NO
2
100 1 1 2
200 2 1 1
NO
Виталик работает на складе. Склад можно представить как поле размером n × m клеток, каждая из которых либо свободна, либо занята контейнером, причем из любой свободной клетки склада можно добраться до любой другой, перемещаясь только между соседними по стороне клетками. Кроме того, на складе находятся два робота. Каждый из них находится в некоторой свободной клетке, и эти клетки различны.
Виталик хочет поменять роботов местами. Роботы могут передвигаться только по свободным клеткам, имеющим общую сторону, кроме того, они не могут одновременно находиться в одной и той же клетке склада или проходить друг сквозь друга. Определить, удастся ли Виталику осуществить свой замысел.
Первая строка содержит два натуральных числа n и m через пробел (2 ≤ n·m ≤ 200000) — размеры склада.
Следующие n строк содержат по m символов каждая. j-й символ i-й строки равен «.», если соответствующая клетка склада свободна, «#», если в ней находится контейнер, «1», если там стоит первый робот, и «2», если там стоит второй робот. Символы «1» и «2» встречаются в этих строках ровно по одному разу.
Выедите «YES» (без кавычек), если роботов можно поменять местами, и «NO» (без кавычек), если этого сделать не удастся.
5 3
###
#1#
#.#
#2#
###
NO
3 5
#...#
#1.2#
#####
YES
У Михахима есть строка s. Он хочет удалить из нее ровно один символ так, чтобы получившаяся строка стала бы палиндромом. Определите, может ли он это сделать, и если да, какой именно символ следует удалить.
Входные данные содержат строку s длины (2 ≤ |s| ≤ 200000), состоящую из строчных латинских букв.
Если решение существует, в первой строке выведите «YES» (без кавычек). В этом случае во второй строке выведите единственное целое число x — номер символа, который нужно удалить из строки s, чтобы получившаяся строка стала бы палиндромом. Считайте, что символы в строке занумерованы с единицы. Если существует несколько таких номеров символов, выведите любой из них.
Если решения не существует, в единственной строке выведите «NO» (без кавычек).
evertree
YES
2
emerald
NO
aa
YES
2
Две лучшие в мире шахматные команды готовятся сыграть друг с другом. Каждая команда состоит из n игроков. У каждого игрока есть рейтинг; игрок с большим рейтингом всегда побеждает игрока с меньшим рейтингом. Известны рейтинги игроков обеих команд: игроки первой команды имеют рейтинги a1, a2, ..., an, а игроки второй команды — рейтинги b1, b2, ..., bn. Среди игроков обеих команд нет игроков, имеющих одинаковый рейтинг.
Шахматный матч между двумя командами состоит из n партий, которые называют партиями на первой, второй, ..., n-й доске. Перед матчем капитан каждой команды должен определить, какой игрок его команды на какой доске будет играть. Выбор капитана другой команды ему при этом неизвестен.
После этого на каждой доске играется по одной партии. Побеждает команда, набравшая больше очков.
Определите для каждой команды, может ли она выиграть.
В первой строке содержится единственное целое число n (1 ≤ n ≤ 200000) — количество игроков в каждой из команд.
Вторая строка содержит n целых чисел ai через пробел (1 ≤ ai ≤ 109) — рейтинги игроков первой команды.
Третья строка содержит n целых чисел bi через пробел (1 ≤ bi ≤ 109) — рейтинги игроков второй команды.
Все ai и bi попарно различны.
Выведите «First», если победить может только первая команда, «Second», если победить может только вторая команда, «Both», если победить может любая команда, и «None», если при любом раскладе будет ничья. Кавычки выводить не нужно.
5
1 3 5 7 9
2 4 6 8 10
Both
5
1 2 3 4 5
6 7 8 9 10
Second
4
9001 9002 1 3
8 6 4 2
First
2
1 1000000000
10000 100000
None
В задачах на строки часто требуется найти строку, обладающую какими-то особыми свойствами. Авторам задачи снова было лень придумывать название для такой строки, поэтому они назвали ее хорошей.
Строка называется хорошей, если она содержит ровно k различных символов. В виде конкатенации какого наименьшего количества хороших строк можно представить данную строку s?
В первой строке содержится целое число k (1 ≤ k ≤ 26).
Во второй строке содержится строка s (1 ≤ |s| ≤ 200000), состоящая из строчных латинских символов.
Выведите через пробел наименьшее количество хороших строк, на которые можно разбить каждый префикс строки s, начиная с префикса, состоящего из первого символа строки, и заканчивая префиксом, совпадающим со строкой. Ведь так тщательнее протестируется, правда?
Если для какого-либо префикса разбиение невозможно, выведите для него «-1».
2
abacaba
-1 1 1 2 2 3 3