<ПРЕД Задача:
СЛЕД>
Задачу решили 38 пользователей: Evgeny, Pupyrev, PetrovSergey, robotact, NSI, DD, Dmitry_Gozman, tomek, Vyshnya, MasterZerg, dragonghy, Cheryl, dan, marek.cygan, liuliang, skywalker, toshiba2, andyzh1314, mikleb, zmy, crazyb0y, tourist, davidsun, Chmeli_BSU, wInuX, Ravent, WsemirZ, zloy_mipt, JohnJones_001, mazahaka, pmnox, defrager, Al.Cash, RAVEman, TTLovePP, ripatti, Dest, avg79.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Шкатулка

Time limit = 5 секунд(ы)

Прямоугольная крышка шкатулки расчерчена на одинаковые квадраты, параллельные сторонам крышки. Вершины квадратов — это узлы получившейся сетки: X × Y узлов (X, Y ≤ 100, X и Y чётные). Узор на крышке выложен одинаковыми драгоценными камнями, вклеенными в узлы. Никакие два камня не могут быть вклеены в один узел. При этом этот узор симметричен относительно обеих осей симметрии крышки шкатулки. Некоторые камни отклеились и потерялись. Необходимо переклеить минимальное количество оставшихся камней так, чтобы рисунок сново стал симметричным.

Требуется написать программу, которая по описанию испорченной шкатулки определяет какие камни следует переклеить. Если есть несколько вариантов решения, то достаточно указать только один.

Вход В первой строке указываются два числа, разделенных пробелами — длины сторон шкатулки. В следующей строке указывается число камней N. Далее следуют N строк с описанием положения камне. В каждой из которых указаны номер и координаты камня, разделенные пробелом.

На рисунке приведен пример шкатулки с потерянными камнями (слева), и шкатулка с симметричным рисунком, который получится после перемещения 4-го и 3-го камня (справа).

Например, для приведенного выше рисунка входные данные будут выглядеть так:

6 4
5 
1 1 3
2 1 1
3 4 3
4 4 2
5 5 3

Выход В первой строчке укажите число переклеенных камней. Для каждого переклееного камня укажите его номер и через пробел его новые координаты. Например, для приведенного входа выход может быть таким:

2
4 5 1
3 3 2

Вход#1
4 12
8
1 1 2
2 3 2
3 1 8
4 1 9
5 1 10
6 3 8
7 3 9
8 3 10
Выход#1
2
4 1 3
6 3 3

Автор:
Школьная олимпиада по информатике Московской области, 8-9 января 2003.
28 января 2003

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 3.228.10.17