Прикреплённый файл «2013-03-22.turtle.py»
Загрузка 1 #!/usr/bin/env python
2 # coding: utf
3 '''
4 «Маршрут черепашки» (MCCME). В левом верхнем углу прямоугольной таблицы размером N×M находится черепашка. В каждой клетке таблицы записано некоторое число. Черепашка может перемещаться вправо или вниз, при этом маршрут черепашки заканчивается в правом нижнем углу таблицы. Подсчитаем сумму чисел, записанных в клетках, через которую проползла черепашка (включая начальную и конечную клетку). Найдите наибольшее возможное значение этой суммы и маршрут, на котором достигается эта сумма.
5 Формат входных данных. В первой строке входных данных записаны два натуральных числа N и M, не превосходящих 100 — размеры таблицы. Далее идет N строк, каждая из которых содержит M чисел, разделенных пробелами — описание таблицы. Все числа в клетках таблицы целые и могут принимать значения от 0 до 100.
6 Формат выходных данных. Первая строка выходных данных содержит максимальную возможную сумму, вторая – маршрут, на котором достигается эта сумма. Маршрут выводится в виде последовательности, которая должна содержать N-1 букву D, означающую передвижение вниз и M-1 букву R, означающую передвижение направо. Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.
7 '''
8
9 import sys
10
11 if len(sys.argv)>1:
12 # Генератор
13 import random
14
15 N=sys.argv[1].isdigit() and int(sys.argv[1]) or random.randint(90,100)
16 M=len(sys.argv)>2 and sys.argv[2].isdigit() and int(sys.argv[2]) or random.randint(N*4/5,N*6/5)
17 print "{0} {1}".format(N,M)
18 print "\n".join((" ".join("{0:3}".format(random.randint(0,100)) for i in xrange(M))) for j in xrange(N))
19 sys.exit(0)
20
21 N,M=(int(k) for k in raw_input().split())
22 A=[[int(k) for k in raw_input().split()] for i in xrange(N)]
23 R=[[0]*M for i in xrange(N)]
24
25 def mxpath():
26 # R -- массив с решениями задачи для каждой клетки
27 R[0][0]=A[0][0]
28 # Строка #0
29 for i in xrange(1,M): R[0][i]=R[0][i-1]+A[0][i]
30 # Столбец #0
31 for j in xrange(1,N): R[j][0]=R[j-1][0]+A[j][0]
32 for s in xrange(2,N+M-1):
33 for i in xrange(max(1,s-M+1),min(N,s)):
34 R[i][s-i]=max(R[i-1][s-i],R[i][s-i-1])+A[i][s-i]
35 return R[N-1][M-1]
36
37 def backagain():
38 i,j,ret=N-1,M-1,""
39 while i or j:
40 if j==0 or i>0 and R[i-1][j]>R[i][j-1]:
41 ret="D"+ret
42 i-=1
43 else:
44 ret="R"+ret
45 j-=1
46 return ret
47
48 mxpath()
49
50 #import pprint
51 #pprint.pprint(A)
52 #pprint.pprint(R)
53
54 print backagain()
Прикреплённые файлы
Для ссылки на прикреплённый файл в тексте страницы напишите attachment:имяфайла, как показано ниже в списке файлов. Не используйте URL из ссылки «[получить]», так как он чисто внутренний и может измениться.- [получить | показать] (2013-03-29 09:45:21, 1.1 KB) [[attachment:2013-03-22.paystep.py]]
- [получить | показать] (2013-03-29 13:21:16, 3.7 KB) [[attachment:2013-03-22.raspil.py]]
- [получить | показать] (2013-03-29 09:48:53, 3.4 KB) [[attachment:2013-03-22.turtle.py]]
- [получить | показать] (2013-03-22 15:22:12, 2.6 KB) [[attachment:oolym-2013-1-b.py]]
- [получить | показать] (2013-03-29 09:48:17, 4.7 KB) [[attachment:oolym-2013-1-bN.py]]
Вам нельзя прикреплять файлы к этой странице.