Найти самый дорогой путь

@FinalSocket · Регистрация: 25.08.2020

Author24 — интернет-сервис помощи студентам

Буратино бежит по полю в Стране дураков и срывает с выросших из его монеток деревьев деньги. За ним гонится Карабас-Барабас, так что времени обходить все деревья нет, можно только пробежать один раз из правого верхнего угла в левый нижний. При этом один раз за всё поле Буратино может воззвать к доброй лисе Алисе, которая добавит ему в карман число монет, равное удвоенной последней цифре текущей суммы у него в кармане. Проложите подходящий маршрут, и укажите, в какой момент лучше обращаться к Алисе.

Формат входных данных
Программа получает на вход через пробел 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
Н Л Л Л Л Л Н А
мой код:

Python

y, x = map(int, input().split())
location =[list(map(int, input().split())) for i in range(y)]
cost = [[0] * x for i in range(y)]
road = [[""] * x for i in range(y)]
cost[0][0] = location[0][0]
location.reverse()
 
for Xelem in range(1, x):
    cost[0][Xelem] = cost[0][Xelem - 1] + location[0][Xelem]
    road[0][Xelem] = road[0][Xelem - 1] + 'Л'
 
for Yelem in range(1, y):
    cost[Yelem][0] = cost[Yelem - 1][0] + location[Yelem][0]
    road[Yelem][0] = road[Yelem - 1][0] + 'Н'
 
for Yelem in range(1, y):
    for Xelem in range(1, x):
        cost[Yelem][Xelem] = max(cost[Yelem][Xelem -1], cost[Yelem - 1][Xelem]) + location[Yelem][Xelem]
        if cost[Yelem][Xelem - 1] > cost[Yelem - 1][Xelem] :
            road[Yelem][Xelem] = road[Yelem][Xelem - 1] + 'Л'
        else :
            road[Yelem][Xelem] = road[Yelem - 1][Xelem] + 'Н'
 
 
print(cost[-1][-1])
print(road[-1][-1] + 'A')

но в ответе вместо 67 выводит 54

@dondublon · 25.08.2020, 18:12

Выводите ваш маршрут, смотрите, где он начал расходиться с эталонным, рабираетесь, почему. Бинго!

@Gdez · 25.08.2020, 18:34

Условие не до конца учел в коде:
После суммирования нужно запоминать (с условием максимума) последнюю цифру суммы и ее индекс = x + y - 1,
Само значение прибавить к итоговой сумме, а букву в маршруте по строковому индексу заменить на "А"

Добавлено через 1 минуту
Почему то у меня ответ по сумме - 58 )))

@DMustache · 26.08.2020, 10:21

как мне сделать последнюю формулу помощи Алисы, чтобы ответ совпадал?

@Gdez · 26.08.2020, 14:03

Уфф...
Одна просьба - ПОСТАРАЙТЕСЬ РАЗОБРАТЬСЯ В КОДЕ, пожалуйста

Python

y, x = map(int, input().split())
location =[list(map(int, input().split())) for i in range(y)]
cost = [[0] * x for i in range(y)]
road = [[""] * x for i in range(y)]
 
##########################################
for i in range(y) :
    location[i].reverse()
#location.reverse() - Так меняются строки, а не столбцы!!!
cost[0][0] = location[0][0]
Amax = cost[0][0]%10
Aindex = 0
k = 1
#####################
 
for Xelem in range(1, x):
    cost[0][Xelem] = cost[0][Xelem - 1] + location[0][Xelem]
    road[0][Xelem] = road[0][Xelem - 1] + 'Л'
 
for Yelem in range(1, y):
    cost[Yelem][0] = cost[Yelem - 1][0] + location[Yelem][0]
    road[Yelem][0] = road[Yelem - 1][0] + 'Н'
 
for Yelem in range(1, y):
    for Xelem in range(1, x):
        cost[Yelem][Xelem] = max(cost[Yelem][Xelem -1], cost[Yelem - 1][Xelem]) + location[Yelem][Xelem]
        if cost[Yelem][Xelem - 1] > cost[Yelem - 1][Xelem] :
            road[Yelem][Xelem] = road[Yelem][Xelem - 1] + 'Л'
        else :
            road[Yelem][Xelem] = road[Yelem - 1][Xelem] + 'Н'
            
##############################################
        k += 1
        if cost[Yelem][Xelem] %10 > Amax :
            Amax = cost[Yelem][Xelem] % 10
            Aindex = k
road[-1][-1] = road[-1][-1][:Aindex] + 'A' + road[-1][-1][Aindex:]
#############################################
 
print(cost[-1][-1] + 2 * Amax)
print(road[-1][-1])

Новые блоги и статьи
Как создать интернет-магазин на PHP и JavaScript InfoMaster 14.01.2025 В современном мире электронная коммерция стала неотъемлемой частью бизнеса. Создание собственного интернет-магазина открывает широкие возможности для предпринимателей, позволяя достичь большей. . .	Как написать Тетрис на Ассемблере InfoMaster 14.01.2025 Тетрис – одна из самых узнаваемых и популярных компьютерных игр, созданная в 1984 году советским программистом Алексеем Пажитновым. За прошедшие десятилетия она завоевала симпатии миллионы людей по. . .	Как создать игру "Танчики" на Unity3d и C# InfoMaster 14.01.2025 Разработка игр – это увлекательный процесс, сочетающий в себе творчество и технические навыки. В этой статье мы рассмотрим создание классической игры "Танчики" с использованием Unity3D и языка. . .	Организую платный онлайн микро-курс по доработке Android-клиента Telegram _Ivana 14.01.2025 Официальная версия и распространенные форки не полностью устраивают? Сделай свою кастомную версию клиента! 4 занятия по 2 часа (2 недели пн, ср 19:00-21:00 по Москве). Первое вводное занятие. . .	Как создать приложение для фитнеса для iOS/iPhone на Kotlin InfoMaster 14.01.2025 Создание собственного фитнес-приложения — это не только захватывающий, но и полезный процесс, ведь оно может стать вашим верным помощником на пути к здоровому и активному образу жизни. В современных. . .	Как создать приложение магазина для iOS/iPhone на Swift InfoMaster 14.01.2025 Введение в разработку iOS-приложений Разработка приложений для iPhone и других устройств на базе iOS открывает огромные возможности для создания инновационных мобильных решений. В данной статье мы. . .
Это работает. Скорость асинхронной логики велика. Вопрос видимо останется в стабильности. Плата - огонь! Hrethgir 13.01.2025 По прошлому проекту в Logisim Evolution https:/ / www. cyberforum. ru/ blogs/ 223907/ blog8781. html прилагаю файл архива проекта Gowin Eda и снимок. Восьмибитный счётчик из сумматора+ генератор сигнала. . .	UserScript для подсветки кнопок языков программирования в зависимости от текущего раздела volvo 13.01.2025 В результате работы этого скрипта подсвечиваются нужные кнопки не только в форме быстрого ответа, но и при редактировании сообщения: / / ==UserScript== / / @name CF_DefaultLangSelect / / . . .	Введение в модели и алгоритмы машинного обучения InfoMaster 12.01.2025 Машинное обучение представляет собой одну из наиболее динамично развивающихся областей искусственного интеллекта, которая фокусируется на разработке алгоритмов и методов, позволяющих компьютерам. . .	Как на Python создать нейросеть для решения задач InfoMaster 12.01.2025 В контексте стремительного развития современных технологий особое внимание уделяется таким инструментам, как нейросети. Эти структуры, вдохновленные биологическими нейронными сетями, используются для. . .	Как создать нейросеть для генерации картинок на Python InfoMaster 12.01.2025 Генерация изображений с помощью искусственных нейронных сетей стала одним из наиболее захватывающих направлений в области компьютерного зрения и машинного обучения. В этой статье мы рассмотрим. . .	Создание нейросети для генерации текста на Python InfoMaster 12.01.2025 Нейросети, или искусственные нейронные сети, представляют собой модели машинного обучения, вдохновленные работой человеческого мозга. Они состоят из множества взаимосвязанных узлов, или "нейронов",. . .

@dondublon 4640 / 2056 / 363 Регистрация: 17.03.2012 Сообщений: 10,139 Записей в блоге: 6
	25.08.2020, 18:12	2
	Выводите ваш маршрут, смотрите, где он начал расходиться с эталонным, рабираетесь, почему. Бинго! 0

@Gdez 8787 / 4442 / 1859 Регистрация: 27.03.2020 Сообщений: 7,271
	25.08.2020, 18:34	3
	Условие не до конца учел в коде: После суммирования нужно запоминать (с условием максимума) последнюю цифру суммы и ее индекс = x + y - 1, Само значение прибавить к итоговой сумме, а букву в маршруте по строковому индексу заменить на "А" Добавлено через 1 минуту Почему то у меня ответ по сумме - 58 ))) 0

@DMustache 1 / 1 / 0 Регистрация: 25.07.2020 Сообщений: 101
	26.08.2020, 10:21	4
	как мне сделать последнюю формулу помощи Алисы, чтобы ответ совпадал? 0

	26.08.2020, 14:03