ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Ural SU Team.GOV contest. Petrozavodsk training camp. Summer 2011

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

H. Магический куб

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Одним из тяжелейших испытаний в истории Энрота стало нападение криган в 1165 году по исчислению Ксина. Однако сохранившиеся после этой войны артефакты дали мощный толчок к развитию магии в Энроте. Принцип работы многих из этих артефактов не понят и по сей день, и лучшие маги проводят бесчисленные исследования и эксперименты в попытках познать их магическую силу.
Одним из таких артефактов являлся магический куб, который, судя по утверждениям участников той войны, в руках криган был способен поддерживать действие заклинаний в течение нескольких дней, позволяя экономить силы магов. Этот куб состоял из большого количества кристаллов эрудина, имеющих форму кубиков одинакового размера. На некоторых гранях этих кристаллов были нарисованы различные руны. При этом, если два кристалла соприкасались гранями, то на этих гранях были нарисованы одинаковые руны. Те грани кристаллов, на которых не было никаких рисунков, в собранном артефакте являлись частями одной из его внешних граней.
К сожалению, до наших дней этот артефакт дошёл уже в виде набора отдельных кристаллов. До сих пор все попытки собрать из них куб были безуспешны — как только несколько кристаллов оказывались достаточно близко, они разлетались во все стороны. Впрочем, учёные даже по разобранному артефакту смогли сделать некоторые выводы. В частности, стало понятно, что большую роль в работе этого артефакта играет расположение его частей друг относительно друга. Теперь исследователи хотят по рунам, нарисованным на гранях кристаллов, попробовать восстановить полную схему расположения кристаллов в собранном артефакте и определить, на каком расстоянии находились друг от друга некоторые из них. Кристаллы можно перемещать и поворачивать произвольным образом.

Исходные данные

В первой строке даны целые числа l и n — длина ребра кристалла и отношение длины ребра всего артефакта к длине ребра одного кристалла (1 ≤ l ≤ 100; 2 ≤ n ≤ 30).
Далее в n3 строках следует описание кристаллов. В каждой из них записаны по шесть целых чисел в пределах от 0 до 109 — номера рун на гранях очередного кристалла согласно справочнику криганских рун Патвина Даркенмора. Число 0 обозначает отсутствие руны на соответствующей грани. Грани описаны в порядке: нижняя, верхняя, правая, левая, передняя, задняя. Гарантируется, что любой ненулевой номер руны встречается в описании кристаллов ровно два раза.
Затем в отдельной строке записано целое число m — количество пар кристаллов, которые интересуют исследователей (1 ≤ m ≤ 10 000). В следующих m строках записаны целые числа a и b — номера кристаллов, расстояние между которыми требуется узнать (1 ≤ a < bn3). Кристаллы пронумерованы в том порядке, в котором они описаны во входных данных.

Результат

Для каждой из перечисленных пар кристаллов выведите в отдельной строке расстояние между центрами этих кристаллов в исходном артефакте с абсолютной или относительной погрешностью не более 10−6.

Пример

исходные данныерезультат
1 2
0 8 73 0 0 16
0 9 0 73 0 1000
0 146 4 0 16 0
0 15 0 4 1000 0
146 0 1 0 6 0
15 0 0 1 2 0
8 0 17 0 0 6
9 0 0 17 0 2
2
1 5
2 8
1.4142135
1
Автор задачи: Михаил Рубинчик (подготовка — Денис Мухаметьянов)
Источник задачи: Ural SU Team.GOV Contest. Petrozavodsk Summer Session, August 2011
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1858. Магический куб