|
Забор
(Время: 2 сек. Память: 16 Мб Сложность: 46%)
Для парка культуры и отдыха было решено изготовить забор. Чтобы забор не портил своим невзрачным видом облик города, архитекторы решили сделать забор фигурным, и разработали несколько различных шаблонов для изготовления секций забора. Шаблон представляет собой многоугольник, где три стороны всегда одинаковы, а четвертая сторона (верхняя часть забора) представляет ломаную линию. Проекции вершин этой ломаной линии на основание забора следуют равномерно, и таким образом шаблон описывается как последовательность высот точек. Высота точек указывается в целых миллиметрах и варьируется от 0 до 2047.
Количество точек в шаблоне равняется L . Архитекторы разработали M шаблонов, и завод изготовил по шаблонам N секций. Пример секции с L = 7 изображен на рисунке.
При транспортировке секций забора до парка произошла авария, и готовые секции забора рассыпались и перемешались. При разборе завалов были выполнены измерения секций, и теперь, зная высоты, необходимо определить, к какому шаблону принадлежит каждая секция забора. Кроме того, при падении секции забора могли быть повреждены (например, могли обломаться зубья забора), поэтому необходимо также посчитать случаи, когда извлечённая из завала секция не совпадает ни с одним шаблоном.
Впрочем, дело несколько упрощается – внутренняя (обращённая в парк) сторона секции отличается по цвету от внешней стороны, поэтому можно сказать с уверенностью, что измерения высот секции проделаны в том же порядке, что и в шаблоне.
Входные данные
Входной файла INPUT.TXT содержит целые значения L – число точек в шаблоне и секции, M – число различных шаблонов, N – число найденных секций (1 ≤ L, M ≤ 1000, N ≤ 1000). Далее M строчек содержат информацию о шаблоне: номер шаблона (натуральное число не более 1000) и L точек шаблона. Далее N строчек содержат информацию о секциях забора, в каждой строке содержится L точек одной секции забора (высота секции от 0 до 8191).
Выходные данные
В выходной файл OUTPUT.TXT следует вывести N строк, каждая строка содержит номер шаблона, с которым совпала секция, либо, если подходящего шаблона не найдено, то выводится символ дефиса '-'. В последней строке теста выводится слово ”OK=” (без кавычек) и число секций, сопоставленных с шаблонами, через пробел символы ”BAD=” и число испорченных секций.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4 2 4
1 250 123 0 66
2 22 31 120 100
250 123 0 66
22 31 120 100
25 31 120 100
250 123 0 66
| 1
2
-
1
OK=3 BAD=1
|
| 2 | 3 3 4
1 55 11 12
3 33 1 2
2 14 15 2
55 11 12
14 15 2
33 1 2
14 15 2
| 1
2
3
2
OK=4 BAD=0
|
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
