img img img img img img img img img img img img img img img img img img img img img img
Логотип Человек живет, пока думает.
Решайте задачи и живите долго!
Для участия в проекте необходимо
и достаточно зарегистрироваться!
Rss Регистрация || Вход
Вход
Diofant.ru
Картинка
Отражение Отражение Картинка Картинка
отражение
Лента событий: georgp решил задачу "Все стороны трапеции" (Математика):
+ 12

Задача 163. Минимальный путь из угла в угол

постоянный адрес задачи: http://www.diofant.ru/problem/495/
показать код для вставки на свой сайт >>
Задачу решили: 29
всего попыток: 47
поделиться задачей:

Задача опубликована: 12.07.09 23:04
Источник: Проект "Эйлер" (http://projecteuler.net)
Вес: 1
сложность: 1 img
класс: 8-10 img
баллы: 100
Темы: алгоритмыimg
Лучшее решение: Oleg (Олег Пилипёнок)

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

Пример кратчайшего пути для таблицы 4 на 4:

40,35,13,32
60,58,40,20
83,18,11,53
72,50,85,75
Длина: 40+35+13+2*20+53+75 = 256

Найдите длину минимального пути в таблице 40 на 40:

71,78,41,12,23,40,74,98,98,92,98,46,63,99,44,46,83,78,18,48,21,84,18,69,41,57,91,25,33,12,63,22,84,18,37,11,15,15,87,47
97,94,72,41,77,43,96,29,72,52,16,18,82,19,36,80,30,89,47,18,77,53,12,30,75,38,81,22,45,37,82,17,17,48,62,67,73,41,57,68
47,45,68,35,13,49,52,11,77,33,37,27,77,16,62,65,68,64,33,96,50,65,22,23,98,14,87,72,48,12,92,63,60,19,85,57,62,12,33,15
91,73,13,75,91,62,27,71,68,17,74,52,34,56,98,13,53,46,42,35,98,55,84,96,68,49,72,16,36,83,66,91,76,30,10,43,80,95,56,21
73,54,92,21,84,84,26,23,80,57,25,62,28,48,43,24,66,34,86,71,55,84,70,23,83,39,80,61,68,33,58,77,59,96,82,87,92,94,29,42
83,58,67,37,19,49,86,26,95,66,66,21,92,14,97,43,40,78,44,77,41,71,30,55,43,32,27,54,55,81,18,64,20,15,10,56,39,17,35,87
90,54,51,34,31,52,32,50,12,13,96,23,57,89,49,88,89,57,67,86,10,62,82,48,87,18,44,53,40,41,48,25,61,43,34,84,78,40,54,71
14,40,51,31,54,50,97,55,79,31,39,41,81,49,98,83,56,91,62,22,60,87,12,91,27,78,68,90,30,63,91,18,16,87,76,84,65,84,54,20
30,12,35,83,93,97,13,11,49,29,42,17,86,56,74,28,40,73,19,65,10,34,12,58,16,64,45,22,39,61,95,24,78,81,95,54,39,36,90,70
59,96,95,97,65,71,11,53,12,60,14,38,11,28,76,44,14,38,49,87,28,41,74,29,62,83,40,47,23,10,79,17,21,96,52,29,65,36,44,75
57,83,50,79,94,43,49,78,64,15,59,34,39,95,80,25,61,97,36,45,38,71,41,78,39,30,24,60,80,36,15,86,40,32,97,78,81,40,92,63
94,69,26,48,99,95,41,99,73,17,64,72,53,29,20,13,34,95,16,38,91,25,19,79,98,32,36,45,43,79,30,81,54,65,45,35,96,28,13,83
21,54,37,78,82,49,45,11,55,11,13,24,12,93,29,46,12,54,66,96,16,96,29,48,77,84,58,73,31,54,74,86,82,52,19,75,51,69,42,67
70,70,15,91,25,43,52,86,71,30,65,25,28,99,24,90,20,84,67,39,59,38,12,83,50,19,47,45,74,32,35,37,66,23,94,77,38,23,37,36
66,30,63,77,56,19,35,38,79,58,58,76,89,64,10,92,15,35,30,57,33,16,53,73,41,43,58,21,31,79,20,17,83,53,90,92,46,33,56,22
85,10,75,47,98,42,15,97,92,60,13,91,30,15,49,86,38,18,62,88,62,87,70,94,63,61,53,86,38,73,38,19,41,91,56,18,75,88,40,66
32,48,53,87,31,78,34,95,65,10,89,80,71,29,99,40,20,96,98,85,96,14,58,42,59,34,58,78,40,83,12,26,35,69,45,21,56,74,53,21
87,13,61,61,15,73,84,20,80,43,43,99,55,31,52,83,50,78,24,48,96,57,37,81,48,11,39,64,64,22,96,78,55,77,21,59,70,40,64,23
13,66,96,85,61,95,64,13,34,88,70,55,64,55,23,98,70,49,39,43,38,21,18,76,52,63,66,31,19,78,43,40,55,62,84,36,57,85,96,63
29,99,59,85,59,88,43,81,75,41,51,55,56,56,22,54,24,51,83,63,29,27,88,16,83,94,94,21,61,28,87,63,11,85,82,30,35,13,13,22
39,12,43,73,90,14,44,99,40,16,23,27,99,76,43,41,75,29,81,22,64,76,49,32,68,52,78,14,97,51,10,14,60,96,86,68,30,15,65,60
88,19,54,41,63,62,95,77,99,40,95,84,76,40,19,57,75,78,80,70,63,61,99,62,19,64,32,66,10,39,77,62,70,98,73,36,11,86,68,72
95,46,13,65,76,86,55,68,75,51,10,50,94,82,12,26,53,63,92,38,78,96,69,29,87,84,45,91,41,45,49,12,90,33,21,79,61,69,76,64
64,91,93,59,45,18,58,34,17,11,29,67,85,53,75,89,20,78,94,68,32,42,19,18,47,79,77,29,94,73,37,45,79,63,10,53,97,63,70,57
17,31,91,79,83,54,55,69,94,16,56,48,82,59,57,12,84,16,99,15,45,24,59,53,91,67,52,10,98,30,84,38,51,49,10,44,45,99,21,96
51,81,69,44,91,38,88,72,99,62,50,90,80,12,11,56,11,54,10,76,91,78,83,23,75,35,35,94,85,36,61,84,57,18,64,90,75,97,88,44
92,21,57,44,19,30,91,94,73,89,90,51,51,33,77,55,47,77,28,19,64,22,37,79,62,80,41,82,46,89,36,52,72,52,43,24,14,35,40,32
10,16,17,90,24,40,70,72,22,42,60,83,18,85,44,54,43,51,96,41,95,36,26,12,35,27,34,33,67,26,45,91,90,30,49,80,15,34,84,25
16,16,61,98,85,30,47,15,62,46,61,82,51,16,63,58,91,25,41,84,38,47,42,82,68,80,49,78,32,56,18,88,32,70,36,36,61,61,63,81
67,81,15,73,80,53,73,93,73,18,84,67,71,10,78,82,35,20,41,46,23,86,35,56,49,24,20,93,40,81,96,19,89,78,30,94,57,38,29,79
45,12,77,84,13,59,45,73,93,88,71,70,70,94,55,80,81,76,38,11,47,84,62,41,64,77,77,57,35,14,66,21,52,71,88,95,93,25,68,90
94,51,62,47,46,81,67,69,81,21,98,35,49,65,79,88,20,29,77,25,62,23,71,17,70,23,97,36,50,26,47,97,40,40,51,22,87,60,92,98
92,95,47,64,18,35,88,57,54,41,16,91,69,47,57,29,66,52,27,26,85,76,58,86,82,53,12,13,55,40,35,85,33,64,38,20,91,81,15,62
28,90,72,39,60,96,39,34,98,89,62,67,32,60,22,76,65,61,20,96,80,45,21,13,76,62,31,88,21,71,43,65,47,92,30,84,63,29,44,82
10,63,97,11,73,65,44,48,27,26,66,87,95,98,49,35,51,77,69,96,17,80,11,56,48,38,19,59,25,91,33,83,92,23,14,99,85,12,14,84
39,48,84,33,96,74,41,32,15,97,24,99,27,71,26,48,20,41,36,49,92,82,59,19,15,60,30,33,68,40,86,18,60,48,97,93,16,86,23,84
48,90,29,93,39,84,15,87,47,68,43,67,17,53,61,99,52,51,96,46,47,50,36,82,31,50,52,97,63,75,69,18,98,66,74,33,46,37,78,83
27,33,58,13,19,27,43,75,54,49,78,39,76,41,97,12,12,72,18,26,91,17,44,39,27,13,60,32,87,66,24,83,99,51,51,56,68,34,86,28
15,89,29,36,10,30,28,66,53,81,61,79,71,87,55,24,57,84,98,40,99,81,93,36,19,66,63,88,66,20,57,81,50,65,91,16,27,70,50,89
88,17,91,50,43,60,52,52,35,35,28,27,79,76,23,90,55,44,32,93,21,30,91,56,18,11,98,26,72,31,23,95,54,31,97,33,19,30,38,51

 
Пожалуйста, не пишите нам, что Вы не можете решить задачу.
Если Вы не можете ее решить, значит Вы не можете ее решить :-)

Обсуждение Правила >>

Внимание! В обсуждении задачи запрещено публиковать ответы и давать подсказки.
 
Внимание! Если Вы увидите ошибку на нашем сайте, выделите её и нажмите Ctrl+Enter.