|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Dashkovsky 2:5002/46.4 16 Jan 2003 23:51:47
To : Vitaly Terekhov
Subject : Задача из олимпиады
--------------------------------------------------------------------------------
15 Янв 03 17:14, you wrote to all:
VT> Кубик находится на некоторой клетки шахматной доски размером 8х8.
VT> Кубик полностью закрывает собой одну клетку доски, т.е. размер ребра
VT> кубика равен размеру стороны клетки доски. Hа каждой стороне кубика
VT> написано какое-то число N (0<=N<=1000). Из начальной клетки кубик
VT> можно премещатьпо доске путем его поворота через соответствующее ребро
VT> на соседнюю клетку. Каждому возможному пути перемещения кубика из
VT> начальной клетки в конечную можно поставить в соответствие
VT> сумму чисел, побывавших на его нижней грани, при этом каждое число
VT> добавляется столько раз, сколько оно появляется на нижней грани
VT> кубика. Числа, соответствующие начальному и конечному положению кубика
VT> тоже суммируются. Путь кубика считается оптимальным. если при
VT> достижении конечной клетки названная сумма оказывается минимальной.
VT> *Требуется* написать программу, котороя определяет оптимальный
VT> путь между двумя заданными клетками и соответствующую ему минимальную
VT> сумму. Hачальная и конечная клетка различны.
VT> *Вводится:* начальное положение кубика (формат e2, e4, f5, f7 -
VT> как в шахматах) и конечное положение, и вводятся числа которые
VT> написаны на гранях кубика.
VT> *Вывод:* минимальна сумма, последовательность премещения кубика.
VT> *Если у кого есть идеи, по поводу того, как реализовать эту задачу на
VT> Паскале,* *то подскажите плз.*
Hе так давно пролетала очень похожая задача, только там было кубик с одной
стороной намазанной клеем и произвольным образом клеем намазанны грани, я
предлагал решать виртуальным графом, т.е. каждая вершина - это все клетки доски
умножить на все положения кубика, хранить надо только один массим на все
вершины, т.е. сам граф не хранится, т.к. наличие вершины вычисляется в процессе,
далее годится волновой дейкстра или нечто подобное.
Andrey
... Ждали Мазая, а пришел Герасим.
--- GoldED+/386 1.1.4.7
* Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Задача из олимпиады