Задача 60: Система защиты (XIV Всероссийская олимпиада по
информатике)
"ПермьОлимпБанк" разработал
сверхнадежную систему защиты ценных бумаг. В правом верхнем углу
любой бумаги должно присутствовать прямоугольное изображение в виде
черно-белого рисунка. Для определения подлинности документов была
создана библиотека контрольных элементов. Если документ подлинный,
то в изображении на документе заданное количество раз присутствует
каждый контрольный элемент из библиотеки. В библиотеке нет
совпадающих элементов.
Система контроля после сканирования получает изображение в виде
цифрового массива N M (N <= 100000, M <= 1000), в котором цифра 1
соответствует черному цвету, а цифра 0 - белому. Затем система ищет
контрольные элементы в полученном массиве.
Контрольный элемент представляется массивом размером L*L (L <= 50)
цифр, каждая из которых равна 0 или 1. В библиотеке - K контрольных
элементов (K 20). Элемент библиотеки должен точно совпадать с
какой-либо частью изображения. При сравнении изображения и
контрольных элементов повороты не допускаются.
Требуется для каждого входного файла сформировать соответствующий
ему выходной файл, в котором записано, сколько раз каждый элемент
библиотеки встречается в изображении, описанном во входном файле.
Входные данные
В каталоге С:\TESTS\6 находятся 13 входных файлов с именами
CONTROL.01, CONTROL.02, ..., CONTROL.13.
В первой строке каждого из этих входных файлов записаны через пробел
числа N, M, K, L.
Далее следуют по порядку К блоков, соответствующих элементам
контрольного образца в библиотеке. Каждый блок состоит из L строк по
L цифр (ноль или единица). После каждого блока следует пустая
строка.
В последующих N строках записаны по M цифр в каждой, соответствующих
изображению.
Выходные данные
Вам требуется сдать 13 выходных файлов с именами:
P"номер участника"_6."номер теста"
где "номер участника" - пятизначный номер участника, 6 - номер
задачи, "номер теста" - двузначный номер теста задачи.
Например, у участника с номером 21111 выходной файл для теста из
файла CONTROL.03 должен называться P21111_6.03
Каждый выходной файл должен содержать К строк.
В каждой строке содержится два числа: номер контрольного элемента из
библиотеки и число его обнаружений (0 - если элемент не обнаружен).
Номер контрольного элемента из библиотеки в первой строке равен 1,
во второй - 2 и т.д.
Все числа в строках должны быть разделены пробелом.
Например, изображению на рис. 1 и контрольным элементам на рис. 2
соответствуют представленные ниже входной и выходной файлы.
|
 |
 |
|
рис. 1 |
рис. 2 |
Входной файл CONTROL.xx
8 7 4 4
1001
1111
1001
1001
1001
1001
1001
1001
0000
0000
0000
0000
0010
1111
0010
0010
1001001
1001001
1001001
1111111
1001001
1001001
1001001
1001001
Выходной файл Pnnnnn_6.xx
1 2
2 2
3 0
4 1
Решение:
Классная задачка! Я больше нигде не видел входных файлов по 100
мегабайт! Ну, теперь перейдем к решению.
На разборе задач после олимпиады нам рассказали, как решить эту
задачу (а частично я решил ее на олимпиаде, но тормозила она жутко)
- но она была последней, а я перестал воспринимать информацию после
3 задачи :), так что придется мне рассказывать свое решение, которое
я придумал сразу после окончания олимпиады :(.
Каждая вертикальная строка контрольного элемента состоит из
произвольного количества нулей и единиц, причем общее количество
этих нулей и единиц меньше либо равно 50. Эту последовательность
можно считать двоичной записью числа, однако в Borland Pascal нет
чисел такой размерности (про double, extended и т.п. молчу - т.к.
они тормозят и не лезут в память), однако во Free Pascal, который
предлагается на олимпиаде вместе с Borland Pascal, существует
целочисленный тип данных int64 и ограничение в памяти помягче - 2Гб.
Free Pascal вы можете скачать на официальном сайте
freepascal.org - советую качать
версию win32 или под Linux(если он у вас есть), потому что go32v2
глючит еще страшнее, чем две предыдущие. Во Free есть несколько
особенностей - в конце надо ставить close(output), потому что
автоматически он этого не делает, ставить скобки в арифметических
выражениях, а то он иногда путает порядок действий (у меня такого не
было - рассказали), и еще: int64 не поддерживает операции mod и не
может быть использован как счетчик в цикле.
Итак, для каждой строки вычислим уникальное число, т.е. которое
однозначно определяет именно эту строку. В случае если нам
встретилась единица, то прибавляем к числу 1 и при каждой новой
встретившейся цифре увеличиваем число вдвое. Вертикальной строке
1111 будет соответствовать число 15, строке 0001 - число 1 и т.п.
Теперь каждый шаблон представлен L числами длиной до 50 двоичных
цифр.
Проведем подобную операцию для первых L строк изображения - получим
до 10000 чисел, каждое из которых длиной до 50 двоичных знаков.
Теперь просто начнем поиск каждого шаблона (50 последовательных
чисел) в строке (10000 последовательных чисел). Это, можно сказать,
поиск подстроки в строке. Для ускорения этого процесса можно
использовать хеш-функции. После того, как мы проверили все шаблоны,
нам необходимо спуститься на одну строку вниз. Для этого из чисел
строки больших либо равных 2^L вычитаем 2^L, т.е. убираем первую
цифру. Теперь умножим полученные числа на 2 (освободим место для
нового ряда. В случае если встретилась 1, то прибавим к числу строки
1. Так будем продолжать до конца входного файла.
Хотелось бы сказать, что заметное ускорение в работе даст
использование вместо типизированного файла нетипизированного, т.к.
Pascal читает из нетипизированного файла намного быстрее.
Далее
ð
