Что я должен сделать, чтобы уменьшить время выполнения моего кода?

Question

Это проблема интернет-судьи по URI (проблема: 1973).

После покупки множества соседних ферм в западном регионе Санта-Катарина семья Звезд построила единую дорогу, которая проходит мимо всех фермы в последовательности. Первая ферма последовательности была названа Звездой 1, вторая Звезда 2 и так далее. Тем не менее, брат, который живет в Звезде 1, разозлился и решил сделать Звездный путь, чтобы украсть овец из владений своих братьев и сестер. Но он определенно сумасшедший. Когда мимо фермы проходит Звезда i, он крадет только одну овцу (если есть) с этой фермы и переходит к Звезде i + 1 или Звезде i - 1, в зависимости от того, было ли количество овец в Звезде i соответственно , нечетное или четное. Если нет Звезды, к которой он хочет go, он останавливает свой путь. Безумный брат начинает свой «Звездный путь» в Звезде 1, крадя овцу с собственной фермы.

Ввод

Первая строка ввода состоит из единственного целого числа N (1 ≤ N ≤ 106), которое представляет количество звезд. Вторая строка ввода состоит из N целых чисел, так что i-е целое число, Xi (1 ≤ Xi ≤ 106), представляет начальное количество овец в Звезде i.

Выход

Выведите строку, содержащую два целых числа, так что первое представляет количество звезд, атакованных безумным братом, а второе - общее количество не украденных овец.

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

#1st solution:
num_star = int(input())
sheep = list(map(int, input().split()))
star = set()
index = 0

while index != num_star:
    if sheep[index] == 0:
        break
    elif sheep[index] % 2 == 1:
        star.add(index)
        sheep[index] -= 1
        index += 1
    else:
        star.add(index)
        sheep[index] -= 1
        index -= 1
        if index == -1:
            break

print(len(star), sum(sheep))

#2nd solution
n = int(input())
x = list(map(int, input().split()))
i = 0
farm_visited = 0
while i in range(n):
    if x[i] == 0:
        if i >= farm_visited: farm_visited = i+1
        break
    elif (x[i]) % 2 == 1:
        if i >= farm_visited: farm_visited = i + 1
        x[i] -= 1
        i += 1
    else:
        if i >= farm_visited: farm_visited = i + 1
        x[i] -= 1
        i -= 1
print(farm_visited, sum(x))

Answer 1

Не читайте ниже, если вы хотите решить это самостоятельно.

def madstar(s): # s is the list
    if all(e % 2 for e in s): # all Stars with odd numbers
        return (len(s), sum(s)-len(s)) # just one sheep stolen from each Star
    for i,e in enumerate(s):
        if e % 2 == 0: # even number found
            return (i+1, # Stars are numbered from 0, so i==0 -> 1 Star visited etc.
                    sum(s) - ( # stolen sheep
                           2*(i+1) # two for every visited Star 
                           - s[:i].count(1) # except visited Stars with initially only 1 sheep
                           - (1 if e>0 else 2) # and the final one, where it is either 0 or 1, but never 2
            ))

for test_list in [[1,3,5,7,11,13,17,19],
                  [1,3,5,7,11,13,16,19],
                  [1],
                  [3,0,2],
                  [0],
                  [2]]:
    print(test_list, '->', madstar(test_list))

Answer 2

решено спасибо @ Błotosmętek и спасибо всем.

def thief(stars, sheep):
    pos_even = 0
    for i in range(stars):
        if sheep[i] % 2 == 0:
            pos_even = i + 1
            last_even_value = sheep[i]
            break
    if pos_even:
        print(pos_even, (sum(sheep) - (pos_even * 2 - sheep[:i].count(1) - (1 if last_even_value > 0 else 2))))
    else:
        print(stars, (sum(sheep) - stars))
num_star = int(input())
s = list(map(int, input().split()[:num_star]))
thief(num_star, s)

Answer 3

Найдите здесь другую (возможно, более простую) реализацию. Не читайте ниже, если вы хотите решить это самостоятельно!

num_star = int(input())
def print_solution(stars_list):
  sheep_taken_when_go = 0
  sheep_taken_when_return = 0
  visited_stars_count = 0
  total_sheep = sum(stars_list)
  for sheep_in_current_star in stars_list:
    visited_stars_count+=1
    sheep_taken_when_go += 1 if sheep_in_current_star>0 else 0 #take one sheep if available
    if sheep_in_current_star%2==0:
      print(visited_stars_count,total_sheep-sheep_taken_when_go-sheep_taken_when_return)
      return
    sheep_taken_when_return += 1 if sheep_in_current_star>1 else 0 #if we ever return, take another sheep if available
  print(visited_stars_count,total_sheep-sheep_taken_when_go)

print_solution(list(map(int, input().split())))