Страница: 1 Отображать по:
#588
Кубики
  
Источники: [ Командные олимпиады, ВКОШП, 2000, Задача F ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Даны кубики с 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
#111663
Доминошахматы
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

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

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

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

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

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

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

Примеры
Входные данные
2 2
1 1
2 2
Выходные данные
NO
Входные данные
2 2
1 1
1 2
Выходные данные
YES
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест