Как улучшить T. C, я получаю TLE - PullRequest
Новая
       26

Как улучшить T. C, я получаю TLE

1 голос
/ 27 мая 2020

Вам дана сетка N x N квадратов. Каждый квадрат, кроме левого верхнего, заполнен положительным целым числом. Вы начинаете с левого верхнего угла со счетом 0 и переходите к правому нижнему квадрату, перемещаясь либо вправо на один квадрат, либо вниз на один квадрат. Когда вы переходите к новому квадрату, ваш счет становится [S / 2] + k, где S - это счет в вашем предыдущем квадрате, а k - это число, записанное в текущем квадрате. Выше [x] - наибольшее целое число, не превышающее x. Таким образом, [5] равно 5, а [5.5] также равно 5.

Напишите программу, чтобы найти наименьший балл, с которым вы можете выйти из сетки.

мой КОД: 

def go(d,r,ans):
    if r==n and d==n:
        ans = ans//2 + arr[d][r]
        return ans
    elif r==n:
        ans = ans//2 + arr[d][r]
        return go(d+1,r,ans)
    elif d==n:
        ans = ans//2 + arr[d][r]
        return go(d,r+1,ans)
    else:
        ans = ans//2 + arr[d][r]
        return min(go(d+1,r,ans),go(d,r+1,ans))

n = int(input())
arr = []
for i in range(n):
    arr.append(list(map(int,input().split())))
ans = 0
n-=1
score = go(0,0,ans)
print(score)

например, тестовый пример: 

2
0 4
9 6

вывод 

8
...