весна 13: Тур 14.03.13

В 2004 году связь с марсоходом "BLR" ("Bulb Location and Rummage"), вот уже несколько лет работавшем на Марсе, была потеряна. Долгое время ученым не удавалось установить с ним связь, и этот проект был приостановлен. Прошло совсем немного времени, и свершилась давняя мечта человечества - на красную планету ступила нога человека.

Изучая более детально поверхность, ученые находили все больше доказательств существовавшей когда-то (а возможно и существующей до сих пор) жизни. Однако этого было не достаточно, и вскоре силы сосредоточились на более детальном изучении того, что находилось под землей. В ходе работ одной из групп ученых, неожиданно были найдены некие подземные ходы. На первый взгляд они выглядели как обыкновенные пещеры, однако позже было выяснено, что природа вряд ли могла создать что-то подобное. Вскоре было найдено еще множество систем, состоящих из пещер и подземных переходов. Все они обладали некоторыми общими свойствами, и ученые предположили, что это остатки марсианских городов.

Систему пещер и переходов ученые считали марсианским городом, если она обладала следующими свойствами:

1. каждый переход соединял только одну пару пещер
2. они располагались в несколько параллельных рядов, причем в каждом из рядов было одинаковое число пещер, а i-е пещеры в рядах (если считать в некотором направлении, одинаковом для всех рядов) также образовывали ровные ряды. Ученые для удобства называли эти ряды соответственно горизонтальными и вертикальными (для каждого из городов это выбиралось произвольно, и принципиального значения не имело). Таким образом, каждая пещера в марсианском городе характеризовалась своим расположением в одном вертикальном и одном горизонтальном ряду
3. из каждой пещеры вело не более четырех переходов - они вели во все пещеры, соседние в горизонтальном и вертикальном рядах.

Вскоре в одной из таких пещер и был найден "BLR". Оказалось, что он уже многие годы ездил по марсианским городам и собирал разнообразную полезную информацию, которую ученые, конечно, хотели бы использовать, поскольку сами они еще не успели изучить все более подробно. Однако некоторые устройства марсохода были давно сломаны, и существовала возможность, что он объезжал одни и те же города по несколько раз. Поэтому, чтобы систематизировать полученную информацию, ученым нужен был способ, чтобы сравнивать описания городов по некоторым критериям и выяснять, описывают ли они один и тот же город. Было известно, что, попадая в город, он обязательно объезжал все переходы между пещерами и запоминал для каждого перехода пару пещер им соединяемых. Также важно было то, что пещеры в городах могли располагаться на различных глубинах. Эта информация и была взята за основу предложенного вскоре метода сравнения.

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

1. для любых двух пещер из первого описания, соответствующие им во втором различны;
2. две пещеры из первого описания соединены (не соединены) переходом только тогда, когда соответствующие им пещеры во втором описании соединены (не соединены) переходом.

Если такое соответствие установлено, и соответствующие города находятся на одинаковых глубинах, то можно было бы считать описания принадлежащими одному городу. Однако, как уже упоминалось выше, не все оборудование марсохода работало стабильно, и поэтому замеры глубин в разное время могли немного отличаться. Поэтому было решено описанным ниже способом вычислять показатель близости, и считать два описания принадлежащими одному городу, если он был достаточно мал.

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

Таким образом, в целом метод сравнения состоял в следующем: найти соответствие между пещерами из двух описаний такое, чтобы оно удовлетворяло описанным выше свойствам, и показатель близости был как можно меньше. Однако такое соответствие не всегда удавалось легко установить, поскольку пещер часто было много, и система переходов могла быть довольно запутанной. Для этого и потребовалась программа, которая для пары описаний городов определяет наименьший из возможных показателей близости.

6 7
17
-10
-32
15
-14
-22
6 5
4 6
3 6
4 2
1 5
2 3
4 1
-12
-22
16
-11
19
-32
2 1
3 2
6 2
3 4
5 1
4 6
3 5

10

4 4
4
-6
2
3
1 2
2 3
3 4
4 1
4
-7
2
4
1 2
2 3
3 4
4 2

incorrect