Динамическое программирование
 Скачать 0.98 Mb.
|
|
А. Рогов) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю. Исключением являются клетки, отмеченные желтым цветом. Находясь в них, робот не может выполнять команду вправо. Перед запуском Робота в каждой клетке квадрата указан бонус, который Робот забирает после посещения клетки. Размер бонуса в каждой клетке – это натуральное число, не превышающее 100. Это правило относится к начальной и конечной клеткам маршрута Робота. Определите минимальную и максимальную суммы бонусов, которые может собрать Робот, перемещаясь из левой верхней клетки квадрата в его правую нижнюю клетку. В ответе укажите два числа: сначала минимальную сумму, затем максимальную. Исходные данные записаны в файле 18-130.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. Пример входных данных:
Для указанных входных данных ответом является пара чисел: 27 41. (А. Рогов) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из трех команд: вправо, вниз или вправо_вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю, по команде вправо_вниз робот перемещается одновременно вправо на одну клетку и вниз на одну клетку, т.е. на одну клетку по диагонали. Исключением являются клетки, отмеченные желтым цветом. Находясь в них, робот не может выполнять команду вниз. Перед запуском Робота в каждой клетке квадрата указан бонус, который Робот забирает после посещения клетки. Размер бонуса в каждой клетке – это натуральное число, не превышающее 100. Это правило относится к начальной и конечной клеткам маршрута Робота. Определите минимальную и максимальную суммы бонусов, которые может собрать Робот, перемещаясь из левой верхней клетки квадрата в его правую нижнюю клетку. В ответе укажите два числа: сначала минимальную сумму, затем максимальную. Исходные данные записаны в файле 18-132.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. Пример входных данных:
Для указанных входных данных ответом является пара чисел: 11 38. (А. Рогов) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из трех команд: вправо, вниз или вправо_вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю, по команде вправо_вниз робот перемещается одновременно вправо на одну клетку и вниз на одну клетку, т.е. на одну клетку по диагонали. Исключением являются клетки, отмеченные желтым цветом. Находясь в них, робот не может выполнять команду вправо. Перед запуском Робота в каждой клетке квадрата указан бонус, который Робот забирает после посещения клетки. Размер бонуса в каждой клетке – это натуральное число, не превышающее 100. Это правило относится к начальной и конечной клеткам маршрута Робота. Определите минимальную и максимальную суммы бонусов, которые может собрать Робот, перемещаясь из левой верхней клетки квадрата в его правую нижнюю клетку. В ответе укажите два числа: сначала минимальную сумму, затем максимальную. Исходные данные записаны в файле 18-132.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. Пример входных данных:
Для указанных входных данных ответом является пара чисел: 16 41. (А. Рогов) Квадрат разлинован на N×N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из трех команд: вправо, вниз или вправо_вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю, по команде вправо_вниз робот перемещается одновременно вправо на одну клетку и вниз на одну клетку, т.е. на одну клетку по диагонали. Исключением являются клетки, отмеченные желтым цветом. Находясь в них, робот может выполнять только команду вправо_вниз. Перед запуском Робота в каждой клетке квадрата указан бонус, который Робот забирает после посещения клетки. Размер бонуса в каждой клетке – это натуральное число, не превышающее 100. Это правило относится к начальной и конечной клеткам маршрута Робота. Определите минимальную и максимальную суммы бонусов, которые может собрать Робот, перемещаясь из левой верхней клетки квадрата в его правую нижнюю клетку. В ответе укажите два числа: сначала минимальную сумму, затем максимальную. Исходные данные записаны в файле 18-134.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата. Пример входных данных:
Для указанных входных данных ответом является пара чисел: 18 36. http://kpolyakov.spb.ru |