В первом классе Глеб увлекался шахматами. К тому моменту он знал только лишь как ходит пешка: она может бить по диагонали влево-вверх и вправо-вверх, и ходить на клетку вверх только если та клетка не занята другой фигурой. О том, что пешка может превращаться в ферзя Глеб не подозревает. Поэтому он придумал свой вариант шахмат.
Игра идёт на доске с N строками и M столбцами (1 ≤ N ≤ 100, 1 ≤ M ≤ 100) по следующим правилам. В нижней строке, имеющей номер 1, стоят P белых пешек, белых фигур на доске больше нет. На остальной части доски стоят разные чёрные фигуры (их названия Глеб не знает). Ходят только белые, их цель — побить все чёрные фигуры.
Как и в настоящих шахматах, если пешка Глеба бьёт чёрную фигуру, то она становится на её место, а побитая фигура убирается с доски. Считается, что Глеб выиграл, если он сумел побить белыми пешками все чёрные фигуры, в противном случае он проиграл. Помогите ему по заданной конфигурации всех фигур определить, сможет ли он выиграть, и, в случае успеха, выведите правильную последовательность ходов белых пешек.
Сначала вводятся четыре целых числа N, M, P, K (1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 0 ≤ P ≤ M, 1 ≤ K ≤ 1000, K ≤ (M - 1)N). Далее записано P различных чисел — номера столбцов pj (1 ≤ pj ≤ M), в которых стоят белые пешки. Далее идут K различных пар целых чисел — координаты (строки и столбцы) чёрных фигур ri, ci (2 ≤ ri ≤ N, 1 ≤ ci ≤ M).
Если пешки не смогут съесть все фигуры, выведите единственное слово NO.
В противном случае в первую строку выведите YES, вторая строка должна содержать суммарное число перемещений C, последующие C строк — описание ходов пешек, по одному ходу на каждую строку. Каждый ход задаётся двумя координатами r, c пешки (номерами строки и столбца), которая будет ходить, и символом m, принимающем три значения: L, R, F — побить вперед и влево, побить вперед и вправо, сделать шаг вперед соответственно. Данные о ходе следует выводить разделёнными одним пробелом, сначала координаты, потом тип хода.
Если последовательностей ходов несколько, выведите любой из них. Обратите внимание, что минимизировать количество перемещений не требуется.
2 2 2 1 1 2 2 2
YES 1 1 1 R
3 3 2 2 1 3 3 1 3 3
NO
Каждый раз, когда в мире происходит значимое событие, наша реальность разветвляется на несколько — в зависимости от исхода этого события. После этого существует уже не только наша основная реальность, но и ответвившиеся от неё в моменты появления разных исходов.
Однажды один архимаг решил сделать мир лучше. Такая грандиозная задача не под силу одному архимагу, поэтому он решил найти самого себя ещё в K реальностях и выполнить эту задачу вместе. Проведённое теоретическое исследование показало, что, кроме реальности, в которой находится именно он, существует ещё N - 1 реальностей. Для удобства они были занумерованы числами от 1 до N, при этом его собственная реальность имеет номер 1, а посетить ему необходимо реальности с номерами 2, 3, ..., K + 1.
Как уже говорилось, каждая реальность когда-то ответвилась от некоторой другой, за исключением одной Начальной реальности, которая существовала всегда (её номер может оказаться каким угодно; считается, что она появилась в момент времени 0). Исследование показало, что реальность с номером i ответвилась от реальности с номером Pi в момент времени Ti. Из каждой реальности с номером i архимаг может переместиться
Требуется найти минимальное количество энергии, которое потребуется архимагу, чтобы, начав в реальности с номером 1, посетить все реальности с номерами от 2 до K + 1 (в любом порядке) и затем вновь вернуться в 1. Любую реальность при этом разрешается посещать сколько угодно раз.
Сначала вводятся два целых числа N и K (0 ≤ K < N ≤ 100 000): количество доступных реальностей и количество реальностей, которые необходимо посетить. Далее идёт N пар целых чисел, i-я пара — это Pi и Ti (1 ≤ Pi ≤ N, 0 ≤ Ti ≤ 106; для Начальной реальности Pi = Ti = 0).
Гарантируется, что ответвившаяся реальность появилась строго позже породившей (Ti > TPi), и что маг может при желании добраться до любой из N реальностей.
Выведите единственное число E — минимальную возможную энергию, которая потребуется архимагу для путешествия.
5 2 4 2 4 6 1 9 0 0 1 7
30
В первом классе Глеб увлекался шахматами. К тому моменту он знал только лишь как ходит пешка: она может бить по диагонали влево-наверх и вправо-наверх, и ходить на клетку вверх только если та клетка не занята другой фигурой. Поэтому он придумал свой вариант шахмат.
Игра идёт на доске с N строками и M столбцами (1 ≤ N ≤ 100, 1 ≤ M ≤ 100) по следующим правилам. В нижней строке, имеющей номер 1, стоит P белых пешек, белых фигур на доске больше нет. На остальной части доски стоят разные чёрные фигуры (их названия Глеб не знает). Ходят только белые, цель — достичь хотя бы одной пешкой самой верхней строки, имеющей номер N (Глеб слышал, что в этой ситуации из пешки можно сделать ферзя, а с такой силой он безусловно сможет побить все остальные чёрные фигуры).
Как и в настоящих шахматах, если пешка Глеба бьёт чёрную фигуру, то она становится на её место, а побитая фигура убирается с доски. Считается, что Глеб выиграл, если он сумел достичь хотя бы одной пешкой самой верхней строки, в противном случае он проиграл. Помогите ему по заданной конфигурации всех фигур определить, сможет ли он выиграть.
Сначала вводятся четыре целых числа N, M, P, K (1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 0 ≤ P ≤ M, 1 ≤ K ≤ (N - 1)M. Далее записано P различных чисел — номера столбцов pj (1 ≤ pj ≤ M), в которых стоят белые пешки. Далее идут K различных пар целых чисел — номера строк и столбцов чёрных фигур ri, ci (2 ≤ ri ≤ N, 1 ≤ ci ≤ M).
Если хотя бы одна пешка сможет достичь последнего ряда, выведите YES, в противном случае выведите NO.
3 3 2 3 1 3 2 2 3 1 3 3
YES
4 4 2 4 1 4 3 1 3 2 4 2 4 4
NO