Задача А. Замок
Задачу добавил: alef
Успешно сдано решений: 2
В НИИ Сверхсекретных методов обработки сверхсекретной информации разработан замок новой системы с многоуровневой защитой.
Каждому сотруднику выдается квадратный брелок, состоящий из n x n маленьких квадратиков. В некоторые из квадратиков интегрированы чипы, содержащие информацию о том, в какие из помещений НИИ и в какое время этот сотрудник может проходить. Сотрудник должен приложить этот брелок к квадратному (также размера n x n) торцу замка, набрать специальный код, после чего записанная на брелоке информация будет прочитана, а дверь - открыта (или не открыта :))
Замок устроен следующим образом. Он состоит из k слоев размером n x n, каждый слой образован кубиками (размер стороны которых совпадает с размером стороны квадратиков, образующих брелок). Первый слой соприкасается с торцом замка, к которому прикладывают брелок. На противоположном торце замка (с ним соприкасается последний, k-ый слой) закреплено устройство (его тоже можно представлять себе состоящим из квадратиков размера n x n), каждый элемент которого отвечает за считывание информации из соответствующего квадратика на брелоке.
В каждом слое некоторые кубики могут быть непрозрачными для считывающего устройства. Будем говорить, что существует просвет с координатами (i,j), если в каждом из k слоев кубик, находящийся на месте (i,j) в слое, является прозрачным для считывающего устройства.
Специальный код приводит в действие механизм замка только в том случае, если все квадратики брелока, содержащие чипы, могут быть распознанными считывающим устройством — т. е. располагаются напротив просветов.
Оказалось, что изготовление непрозрачных кубиков обходится в несколько раз дороже прозрачных. Кроме того, оказалось, что непрозрачные кубики плохо склеиваются друг с другом.
Руководство НИИ решило выделить для создания каждого замка по k непрозрачных кубиков, которые, по мнению руководства, должны быть помещены по одному в каждый слой, что должно обеспечить приемлемую стоимость и надежность конструкции.
Также руководство НИИ поручило программисту Кеше Канарейкину разработать программу, которая по заданному набору описаний брелоков определяет, достаточно ли заданного количества непрозрачных кубиков для того, чтобы владельцы этих брелоков не могли открыть замок, а также предлагает возможное размещение непрозрачных кубиков.
Формат входного файла input.txt
Первая строка — целые числа n и k (1 <= n, k <= 100) через пробел
Вторая строка — целое число m (1 <= m <= 1000) — количество описаний брелоков
Следующие m строк содержат описания брелоков в формате
первое число — целое число Bj (j = 1, 2, ..., m; 1 <= Bj <= n^2) — количество квадратиков с чипами. За ним через пробел следуют пары чисел i1 j1 i2 j2 ... - координаты (строка и столбец) квадратиков с чипами. Числа в паре и пары между собой отделяются пробелами
PS Имейте в виду, что, поскольку брелоки квадратные, сотрудники могут их поворачивать на угол, кратный Pi/2, прикладывая к торцу замка.
PPS Размер входного файла не превышает 4 Мб
Формат выходного файла output.txt
Первая строка - YES или NO - хватит или не хватит непрозрачных кубиков, чтобы "перекрыть" все брелоки
Следующие k строк (в случае ответа YES) - возможное расположение непрозрачных кубиков, в каждой строке - 3 числа: i, j, p - их координаты.
|
Пример входного файла 10 8 3 4 2 2 7 6 3 5 4 9 3 3 4 6 8 5 3 2 9 6 3 5 |
Пример выходного файла YES 3 5 1 5 8 2 6 3 3 8 6 4 3 4 5 3 6 6 8 7 7 1 1 8 |