Объяснение:
Эта задача сводится к задаче поиска пути на графе пространства состояний.
Состояние - положение черепашки на поле - (x, y).
Граф пространства состояний состоит из таких вершин-состояний, их количество N * M.
Переходов между вершинами всего два: R и D.
Здесь можно заметить, что прийти к одним и тем же вершинам мы можем разными путями. Например, путь из (0,0) в (1,1) можно расписать и как RD ((0,0) -> (0,1) -> (1,1)), и как DR ((0,0) -> (1,0) -> (1,1)), но это два разных маршрута.
Однако при неизменном ценовом листе максимальная стоимость и оный маршрут в любой клетке поля значение строго определённое и неизменное во времени.
Это значит, что нам не нужно рассчитывать результат для одинаковых состояний больше одного раза, так как они будут совпадать.
Итак, для каждого состояния у нас есть два правила перехода. Рассчитывая максимальную стоимость маршрута для состояния (x,y) мы следуем алгоритму:
Если можем идти вправо, рассчитываем параметры для этого маршрутаЕсли можем идти вниз, рассчитываем параметры для этого маршрутаВыбираем между путями, если можем идти, или стоим, если уже не можемК выбранному варианту добавляем параметры текущего состоянияЕсли такой алгоритм применить к состоянию (0,0), то дойдем до (N, M) и получим максимальную цену и маршрут.
Код:
import re
from typing import List
cache = {}
def calculate_max_way_price(x: int, y: int, prices: List[List[int]], m:int, n:int):
if (x, y) in cache:
return cache[(x, y)]
direction = ''
cost = prices[y][x]
x_cost, y_cost = -1, -1
x_way, y_way = '', ''
if x < m - 1:
x_cost, x_way = calculate_max_way_price(x + 1, y, prices, m, n)
if y < n - 1:
y_cost, y_way = calculate_max_way_price(x, y + 1, prices, m, n)
if not (x_cost < 0 and y_cost < 0):
if x_cost > y_cost:
cost += x_cost
direction = 'R' + x_way
else:
cost += y_cost
direction = 'D' + y_way
cache[(x, y)] = (cost, direction)
return cost, direction
MNtext = input('Enter N M: ')
MN = [int(x) for x in re.findall(r'\d+', MNtext)]
if len(MN) != 2:
print("Input data error! It is not M and N")
exit(-1)
N, M = MN[0], MN[1]
MAX_STEP_PRICE = 100
data = input('Enter all numbers separated by spaces. You must type ' + str(M*N) + ' elements:')
data = [int(x) for x in re.findall(r'\d+', data)]
if len(data) != N * M:
print("Input data error! Too few/many numbers")
exit(-2)
prices = []
for j in range(N):
prices.append(data[M*j:M*(j+1)])
print(calculate_max_way_price(0, 0, prices, M, N))
Объяснение:
Сочинение на тему: Наше будущее в наших руках
В современном мире достаточно трудно найти человека, который не хотел бы узнать свое будущее. Каждый из нас неоднократно задумывался над вопросом: что с нами будет через несколько лет? ответ на это вопрос ищут в знахарей или колдунов. Однако мало кто склоняется к мысли, что наше будущее зависит только от нас самих, только мы его менять.
Народная пословица гласит: «Каждый человек — кузнец своего счастья». Трудно не согласиться с этим мнением, ведь в мире не существует такой силы, которая построила бы наше будущее за нас.
Я склоняюсь к мысли, что каждому из нас под силу творить свою собственную жизнь. В мире существует множество примеров, когда люди, благодаря своему труду, настойчивости и таланта, достигали невероятных высот. На эту землю все приходят равными, однако свое будущее каждый строит сам.
Я считаю, что в жизни нельзя изменить только две вещи: дату рождения и дату смерти. Все остальное в наших руках. Существуют люди, которые готовы оспорить этот тезис, однако другие разделяют со мной такую позицию. Если человек верит в светлое будущее и готов для этого упорно работать, то очевидным фактом является то, что он достигнет невероятного успеха.
Ярким примером создателей светлого будущего есть народ, который пережил много лет порабощения через кровавые страдания, пережил нечеловеческие издевательства, но все это время боролся за собственную независимость и собственноручно ее получил. Ведь будущее страны было лишь в руках его народа, который благодаря своему несокрушимому духу сумел построить сильное, независимое государство.
Итак, исходя из всего выше сказанного, можно сделать вывод, что судьба каждого человека зависит только от него самой. Каждый из нас — творец собственного счастья. Наше будущее зависит от того, что мы будем делать сейчас. И начинать нужно уже сейчас, закладывая маленькие кирпичики в свой дом под названием «будущее». И всегда следует помнить, что наше будущее, в наших руках, главное их не опускать!