#588

Кубики

Темы: [Паросочетания] [Потоки]

Источники: [ Командные олимпиады, ВКОШП, 2000, Задача F ]

Даны кубики с 6 буквами написанными на них и слово. Требуется составить слово из кубиков.

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

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

Дан набор кубиков и имя сестры. Выясните, можно ли выложить ее имя с помощью этих кубиков и если да, то в каком порядке следует выложить кубики.

Входные данные

В первой строке вводится число \(N\) (1 <= \(N\) <= 100) - количество кубиков в наборе у Пети. Во второй строке задано имя Петиной сестры - слово, состоящие только из больших латинских букв, не длиннее 100 символов. Следующие N строк содержат по 6 букв (только большие латинские буквы), которые написаны на соответствующем кубике.

Выходные данные

В первой строке выведите "YES" если выложить имя Петиной сестры данными кубиками можно, "NO" в противном случае.

В случае положительного ответа, во второй строке выведите \(M\) различных чисел из диапазона 1…\(N\), где \(M\) - количество букв в имени Петиной сестры. \(i\)-е число должно быть номером кубика, который следует положить на \(i\)-е место при составлении имени Петиной сестры. Кубики нумеруются с 1, в том порядке, в котором они заданы во входных данных. Если решений несколько, выведите любое. Разделяйте числа пробелами.

Примеры

Входные данные

2
AB
AAAAAB
AAAAAA

Выходные данные

YES
2 1

Входные данные

3
ANNY
AAAAAA
NNNNNN
YYYYYY

Выходные данные

NO

#2512

Поедание сыра

Темы: [Потоки]

Источники: [ Командные олимпиады, ВКОШП, 2009, Задача A ]

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

Всего на заводе живет \(m\) мышей. Для \(i\)-й мыши известна ее скорость поедания сыра \(s_i\), мышь может съесть \(s_i\) грамм сыра в час.

Недавно мышам стал известен план работы завода на ближайшее время. Планируется изготовить \(n\) головок сыра. Про каждую головку известны \(r_i\) к началу какого часа она будет изготовлена, \(d_i\) в начале какого часа она начнет портиться, и \(p_i\) вес головки сыра в граммах.

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

Мыши не любят есть сыр после того как он начал портиться. Но оставлять сыр недоеденным мыши не могут. Они решили организовать поедание сыра таким образом, чтобы величина \(t\), такая что какую-либо головку все еще продолжают есть через \(t\) часов после того как она начала портиться, была минимальна. Помогите мышам выяснить, как это сделать.

Входные данные

Первая строка входного файла содержит два целых числа \(n\) и \(m\) (\(1 \le n \le 30\), \(1 \le m \le 30\)). Следующие \(n\) строк содержит по три целых числа: \(p_i\), \(r_i\) и \(d_i\) (\(1 \le p_i \le 10^5\), \(0 \le r_i \lt d_i \le 10^7\)). Далее следуют \(m\) строк, каждая из которых содержит по одному целому числу \(s_j\) (\(1 \le s_j \le 10^5\)).

Выходные данные

Выведите одно вещественное число — искомое минимальное \(t\). Ваш ответ должен отличаться от правильного не больше чем на \(10^{-4}\).

Комментарий к примеру тестов

В первом примере мышам следует организовать поедание сыра следующим образом. Сначала первая мышь начинает есть первую головку сыра. Когда появляется вторая головка, она перестает есть первую и начинает есть вторую (в этот момент от первой осталось 9 граммов). Вторая мышь принимается есть первую головку сыра. Через 2.5 часа первая мышь доедает вторую головку сыра (на 0.5 часа позже чем она начала портиться) и снова начинает есть первую (вторая мышь за это время съела еще 5 граммов от первой головки и от нее осталось 4 грамма). Таким образом еще за час первая мышь доедает первую головку, также на 0.5 часа позже чем она начала портиться.

Во втором примере мышь успевает съесть сыр до того как он начинает портиться

Примеры

Входные данные

Выходные данные

0.5

Входные данные

1 1
1 0 1
1

Выходные данные

0.0

#2821

Пешки

Темы: [Потоки]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2010, Лига А, Задача H ]

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

Игра идёт на доске с 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 различных чисел — номера столбцов p_j (1 ≤ p_j ≤ M), в которых стоят белые пешки. Далее идут K различных пар целых чисел — координаты (строки и столбцы) чёрных фигур r_i, c_i (2 ≤ r_i ≤ N, 1 ≤ c_i ≤ M).

Выходные данные

Если пешки не смогут съесть все фигуры, выведите единственное слово NO.

В противном случае в первую строку выведите YES, вторая строка должна содержать суммарное число перемещений C, последующие C строк — описание ходов пешек, по одному ходу на каждую строку. Каждый ход задаётся двумя координатами r, c пешки (номерами строки и столбца), которая будет ходить, и символом m, принимающем три значения: L, R, F — побить вперед и влево, побить вперед и вправо, сделать шаг вперед соответственно. Данные о ходе следует выводить разделёнными одним пробелом, сначала координаты, потом тип хода.

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

Примеры

Входные данные

2 2 2 1
1 2
2 2

Выходные данные

YES
1
1 1 R

Входные данные

Выходные данные

NO

#2831

Пешки

Темы: [Потоки]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2010, Лига Б, Задача H ]

В первом классе Глеб увлекался шахматами. К тому моменту он знал только лишь как ходит пешка: она может бить по диагонали влево-наверх и вправо-наверх, и ходить на клетку вверх только если та клетка не занята другой фигурой. Поэтому он придумал свой вариант шахмат.

Игра идёт на доске с 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 различных чисел — номера столбцов p_j (1 ≤ p_j ≤ M), в которых стоят белые пешки. Далее идут K различных пар целых чисел — номера строк и столбцов чёрных фигур r_i, c_i (2 ≤ r_i ≤ N, 1 ≤ c_i ≤ M).

Выходные данные

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

Примеры

Входные данные

Выходные данные

YES

Входные данные

Выходные данные

NO

#111663

Доминошахматы

Темы: [Жадный алгоритм] [Потоки] [Паросочетания]

Источники: [ Командные олимпиады, Турнир Архимеда, 2013, Задача D ]

Вася очень любит различные игры: шашки, шахматы, домино, крестики-нолики и т. д. Поскольку он играет в них уже достаточно давно, он успел изучить эти игры достаточно хорошо, и они стали скучными. Поэтому он теперь изобретает новые игры на основе тех, в которые уже наигрался. Недавно он изобрел игру «Доминошахматы».

Она состоит в следующем: Вася берет у дедушки большой кусок фанеры и раскрашивает его так, что у него получается шахматная доска размера N × M клеточек. Потом он берет кости домино и пытается покрыть ими полученную доску так, чтобы все клеточки были закрыты, не было наложений и никакие доминошки не торчали за края доски (каждая доминошка покрывает две соседние клетки).

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

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

Помогите Васе понять, можно ли это сделать.

Входные данные

В первой строке входных данных записаны числа N и M — размеры доски (1 ≤ N ≤ 200, 1 ≤ M ≤ 200, N·M > 2).

Во второй строке вводятся через пробел два целых числа — координаты x₁ и y₁ первой вырезанной клетки (1 ≤ x₁ ≤ N, 1 ≤ y₁ ≤ M).

В третьей строке вводятся через пробел два целых числа — координаты x₂ и y₂ второй вырезанной клетки (1 ≤ x₂ ≤ N, 1 ≤ y₂ ≤ M).

Первая и вторая клетки не совпадают.

Выходные данные

Выведите «YES», если доску с вырезанными клеточками можно покрыть доминошками, и «NO» в противном случае. (Запас доминошек у Васи бесконечный.)

Примеры

Входные данные

2 2
1 1
2 2

Выходные данные

NO

Входные данные

2 2
1 1
1 2

Выходные данные

YES