printРабочее место участника

printЗадачи

1755. Забор

Ограничения: время – 6s/12s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Для парка культуры и отдыха было решено изготовить забор. Чтобы забор не портил своим невзрачным видом облик города, архитекторы решили сделать забор фигурным, и разработали несколько различных шаблонов для изготовления секций забора. Шаблон представляет собой многоугольник, где три стороны всегда одинаковы, а четвертая сторона (верхняя часть забора) представляет ломаную линию. Проекции вершин этой ломаной линии на основание забора следуют равномерно, и таким образом шаблон описывается как последовательность высот точек. Высота точек указывается в целых миллиметрах и варьируется от 0 до 2047.
Количество точек в шаблоне равняется `L` (`1\ ≤\ L\ ≤\ 100`). Архитекторы разработали `M` шаблонов (`1\ ≤\ M\ ≤\ 10000`), и завод изготовил по шаблонам `N` секций (`1\ ≤\ N\ ≤\ 100000`).
При транспортировке секций забора до парка произошла авария, и готовые секции забора рассыпались и перемешались. При разборе завалов были выполнены измерения секций, и теперь, зная высоты, необходимо определить, к какому шаблону принадлежит каждая секция забора. Кроме того, при падении секции забора могли быть повреждены (например, могли обломаться зубья забора), поэтому необходимо также посчитать случаи, когда извлечённая из завала секция не совпадает ни с одним шаблоном.
Впрочем, дело несколько упрощается – внутренняя (обращённая в парк) сторона секции отличается по цвету от внешней стороны, поэтому можно сказать с уверенностью, что измерения высот секции проделаны в том же порядке, что и в шаблоне.
Все данные разделяются одним пробелом. Последние данные в строке завершаются символом перевода строки. Первая строка содержит количество тестов. Далее идут данные тестов.
Первая строка данных теста содержит значения `L` (число точек в шаблоне и секции), `M` (число различных шаблонов), `N` (число найденных секций). Далее `M` строчек содержат информацию о шаблоне: номер шаблона (натуральное число) и `L` точек шаблона. Далее `N` строчек содержат информацию о секциях забора, в каждой строке содержится `L` точек одной секции забора.
В первой строке выводится слово TEST и через пробел номер теста.
Затем следует `N` строк, каждая строка содержит номер шаблона, с которым совпала секция, либо, если подходящего шаблона не найдено, то выводится символ '-' (минус).
В последней строке теста выводится слово "OK=" (без кавычек) и число секций, сопоставленных с шаблонами, через пробел символы "BAD=" и число испорченных секций.

Пример ввода

2
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
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

Пример вывода

TEST 1
1
2
-
1
OK=3 BAD=1
TEST 2
1
2
3
2
OK=4 BAD=0
Четвертьфинальные соревнования Чемпионата мира Восточно-сибирского региона, 2008
loading