Главное меню портала
• О портале
• Архив задач
• Карта архива задач
• Результаты тестов
• Ошибки тестирования
• Преподаватели
• Библиотечка
Рейтинг у учителя
• Рейтинг на портале
Начинающему
• Работа с порталом
• Курс для начинающего
• Архив задач начинающего
Олимпиаднику
• Архив задач олимпиадника
Олимпиады
Дистанционные олимпиады
• Положение олимпиады
Новое сообщениеОтправленые
Загрузка...
Время на прохождение теста: 1 секунд(а/ы).
Имя входного файла: input.txt
Имя выходного файла: output.txt

Автор: Бельский Андрей Владимирович

Сон шамана

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

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

Куб имеет размерность N*N*N*N, каждая его ячейка определяется 4 координатами (x, y, z, w), каждая из которых может принимать значения от 0 до N-1. Из каждой ячейки можно перейти в 8 соседних за время, указанное на карте для этой ячейки. Соседняя ячейка - это ячейка, у которой одна из координат отличается на 1, т.е., например ячейка с координатами (x, y, z+1, w). Поясним свернутость куба в сферу на примере переходов из ячейки (0, 0, 0, 0). При размерности куба больше 2 возможно 8 различных переходов в ячейки: (0, 0, 0, 1), (0, 0, 1, 0), (0, 1, 0, 0), (1, 0, 0, 0), (0, 0, 0, N-1), (0, 0, N-1, 0), (0, N-1, 0, 0), (N-1, 0, 0, 0). При N=2 возможно всего 4 перехода, т.к. N-1=1. Т.е. каждая координата берется по модулю N. Переход в любую из соседних ячеек занимает одинаковое время, указанное на карте для данной ячейки.

Т.к. у шамана еще много дел, то он хочет как можно быстрее добраться до выхода из куба.

Входные данные:

 Во входном файле записано целое число N - размер куба (2 <= N <= 10). Далее записано два набора из четырех чисел - координаты начальной и конечной ячеек и, далее, N4 целых чисел Mi (1 <= Mi <= 1 000), описывающих карту. При этом индекс i = x*N3 + у*N2 + z*N + w, i изменяется последовательно от 0 до N4-1.

Выходные данные:

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


Примеры:
input.txt output.txt
1 2
0 0 0 0
1 1 1 1
1 2 7 25 10 15 64 17 10 7 12 45 10 15 46 13
25

Сложность задачи: 20%



Проверку могут осуществлять только зарегистрированные пользователи!


Показать обсуждение


На сайте гостей 37, зарегистрированных 3:
Marichka, cor Sabrr, Fate,
[Данные за последние 5 минут]