Question

Буратино бежит по полю в Стране дураков и срывает с выросших из его монеток деревьев деньги. За ним гонится Карабас-Барабас, так что времени обходить все деревья нет, можно только пробежать один раз из правого верхнего угла в левый нижний. При этом один раз за всё поле Буратино может воззвать к доброй лисе Алисе, которая добавит ему в карман число монет, равное удвоенной последней цифре текущей суммы у него в кармане. Проложите подходящий маршрут, и укажите, в какой момент лучше обращаться к Алисе. Формат входных данных Программа получает на вход через пробел r, c - количество строк и столбцов в матрице (количество рядом деревьев и деревьев в ряду). Потом r строк, каждая из которых состоит из c чисел, разделённых пробелами. Каждое число соответствует количеству монет, которые можно собрать с данного дерева. Все числа целые, в пределах от 1 до 100 включительно. Формат выходных данных Программа выводит на экран наибольшее количество монет, которое может собрать Буратино, если он будет идти от верхнего правого угла поля до нижнего левого угла включительно. Он может перемещаться только вниз и влево. При этом, когда он попадает на клетку с числом Х, количество монет у него увеличивается на Х. Также один раз после перехода в какую-то клетку дополнительно Буратино добавится 2Х монет, где Х - младшая цифра в количестве монет в его кармане на момент прихода в данную клетку. После количества монет программа выводит маршрут Буратино, состоящий из букв Н (вниз), Л (влево), А (Алиса), суммарно букв должно быть r + c - 1. Буква А встречается в маршруте ровно один раз, при одинаковых итоговых суммах - как можно раньше. Буквы разделены пробелами. Ввод: 3 6 6 3 7 8 5 7 6 9 1 7 9 9 1 1 4 3 2 5 Вывод: 67 Н Л Л Л Л Л Н А