Задача 46: Программистика
XIV Всероссийская олимпиада по информатике. 5-11 апреля 2002г. г.
Пермь.
В Перми становится популярной игра "Программистика".
Для игры требуются плоские квадратные фишки 4-х видов,
представляющие собой поле 3*3 с вырезанной центральной клеткой. В
остальных клетках каждой фишки записаны числа от 1 до 8. Все виды
фишек показаны на рисунке. Количество фишек каждого вида не
ограничено.
Игра проводится на поле размером N*N. Первоначально все клетки поля
заполнены единицами.
В начале игры Магистр несколько раз случайным образом помещает
произвольные фишки на игровое поле так, что фишка попадает на поле
целиком, а ее центральная клетка совпадает с одной из клеток поля.
После помещения очередной фишки все числа в восьми клетках игрового
поля, которые перекрывает фишка, умножаются на соответствующие числа
в клетках фишки, и результаты становятся новыми значениями этих
клеток игрового поля.
Таким образом, после окончания процесса размещения фишек игровое
поле оказывается заполненным полученными произведениями. Далее
Магистр передает получившееся поле игроку, которому необходимо
установить для каждой клетки поля, сколько раз Магистр в нее помещал
центральные клетки фишек.
Требуется для каждого входного файла, содержащего полученное
Магистром поле, сформировать соответствующий ему выходной файл, в N
строках которого содержится по N чисел, показывающих, сколько раз в
соответствующую клетку помещались центральные клетки фишек.
Входные данные
В каталоге C:\TESTS\4 находятся 7 входных файлов с именами
game.01, game.02, :, game.07. В первой строке каждого из этих файлов
записано N (3 < N < 100). В последующих N строках записано по N
разделенных пробелами натуральных чисел, являющихся значениями
полученных Магистром произведений, каждое из которых не превышает
2*10^9.
Выходные данные
Каждый выходной файл должен состоять из N строк по N разделенных
пробелами чисел, показывающих для каждой клетки поля, сколько раз в
нее помещались центральные клетки фишек.
Вам требуется представить на тестирование 7 выходных файлов с
именами:
Р[номер участника]_4.[номер теста]
где <номер участника> - пятизначный номер участника, 4 - номер
задачи, <номер теста> - двузначный номер теста задачи.
Например, у участника с номером 21111 выходной файл для теста № 3
должен называться P21111_4.03
Пример
Входной файл game.0x
5
1 2 3 1 1
8 1 140 48 7
7 6 120 1 16
1 1 15 8 3
1 1 1 1 1
Выходной файл Р21111_4.0x
0 0 0 0 0
0 1 0 0 0
0 0 0 2 0
0 0 0 0 0
0 0 0 0 0
Примечание
Результатом решения задачи являются только 7 выходных файлов,
которые и необходимо представить на проверку.
Решение:
Это самая простая задача на олимпиаде имеет нестандартный вид. Здесь
необходимо сдать не программу, а только выходные файлы, но чтобы их
сгенерировать, все-таки нужно написать программку :)
Начнем просматривать игровое поле с левого верхнего угла(на верхней
левый угол может влиять только карточка с центром в
(2;2)). Будем пытаться поставить на клетку (2;2) все карточки, за
исключением карточки номер 1. В случае, если карточку подставить
можно, увеличиваем счетчик в точке (2;2) на 1, а значения окружающих
ее клеток делим на числа, написанные на соответствующем месте
карточки. Как только мы не сможем подставить ни одну из карточек с
номерами от 2 до 4, перейдем к карточке 1(мы не переходили к ней
раньше, т.к. неизвестно . Рассмотрим поле (2;1): у первой карточки
на это место приходится число 2, у всех остальных числа: 7, 5, 3.
Надо заметить что никакая комбинация из перемноженных чисел 3, 5 и 7
не даст 2^k, т.к. будет нечетной. Проверим, на какую степень 2 мы
можем разделить значение (2;1). Соответственное количество первых
карточек имеет центр в точке (2;2). Обработаем для них другие
покрываемые клеточки
Теперь представим, что самой верхней левой клеткой стала клетка
(2;1). Повторим для нее те же операции. Когда мы достигнем верхней
левой клетки (N - 2; 1) следующей за ней будет верхняя левая клетка
(2;2). Повторим эту операцию, пока не проверим все поле. Если вы
обработали все правильно, то оно должно быть заполнено единичками.
Далее
ð
