Задача из олимпиады

From

Andrey Dashkovsky (2:5002/46.4)

To

Vitaly Terekhov

Date

2003-01-16T22:51:47Z

Area

RU.ALGORITHMS

Hello Vitaly.

15 Янв 03 17:14, you wrote to all:

 VT>  Кубик находится на некоторой клетки шахматной доски размером 8х8.
 VT> Кубик полностью закрывает собой одну клетку доски, т.е. размер ребра
 VT> кубика равен размеру стороны клетки доски. На каждой стороне кубика
 VT> написано какое-то число N (0<=N<=1000). Из начальной клетки кубик
 VT> можно премещатьпо доске путем его поворота через соответствующее ребро
 VT> на соседнюю клетку. Каждому возможному пути перемещения кубика из
 VT> начальной клетки в конечную можно поставить в соответствие
 VT> сумму чисел, побывавших на его нижней грани, при этом каждое число
 VT> добавляется столько раз, сколько оно появляется на нижней грани
 VT> кубика. Числа, соответствующие начальному и конечному положению кубика
 VT> тоже суммируются. Путь кубика считается оптимальным. если при
 VT> достижении конечной клетки названная сумма оказывается минимальной.

 VT>      *Требуется* написать программу, котороя определяет оптимальный
 VT> путь между двумя заданными клетками и соответствующую ему минимальную
 VT> сумму. Начальная и конечная клетка различны.

 VT>      *Вводится:* начальное положение кубика (формат e2, e4, f5, f7 -
 VT> как в шахматах) и конечное положение, и вводятся числа которые
 VT> написаны на гранях кубика.

 VT>      *Вывод:* минимальна сумма, последовательность премещения кубика.

 VT> *Если у кого есть идеи, по поводу того, как реализовать эту задачу на
 VT> Паскале,* *то подскажите плз.*

Не так давно пролетала очень похожая задача, только там было кубик с одной
стороной намазанной клеем и произвольным образом клеем намазанны грани, я
предлагал решать виртуальным графом, т.е. каждая вершина - это все клетки доски
умножить на все положения кубика, хранить надо только один массим на все
вершины, т.е. сам граф не хранится, т.к. наличие вершины вычисляется в процессе,
далее годится волновой дейкстра или нечто подобное.

Andrey

... Ждали Мазая, а пришел Герасим.
--- GoldED+/386 1.1.4.7
 * Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)