Кикстарт 2020, раунд B TLE - PullRequest
Новая
       19

Кикстарт 2020, раунд B TLE

0 голосов
/ 20 апреля 2020

Я участвовал в раунде B по кикстарту Google. На вопрос Bus Routes я написал код, который работает для первого набора тестов. Но для второго контрольного примера это ошибка превышения лимита времени. Я написал этот код в Python, и я не знаю, как его оптимизировать, может кто-нибудь рассказать мне обо всех изменениях в моем коде, чтобы он работал без каких-либо ошибок.

Ниже приводится вопрос:

Задача

Ведро планирует совершить очень долгий путь по сельской местности на автобусе. Ее путешествие состоит из N автобусных маршрутов, пронумерованных от 1 до N в том порядке, в котором она должна их проехать. Сами автобусы очень быстрые, но ходят не часто. I-й автобусный маршрут курсирует только каждые Xi дни.

В частности, она может сесть на i-й автобус только в день Xi, 2Xi, 3Xi и т. Д. Поскольку автобусы очень быстрые, она может сесть на несколько автобусов в один и тот же день.

Ведро должно завершить sh свое путешествие ко дню D, но она хотела бы начать путешествие как можно позже. Какой самый последний день, когда она могла сесть на первый автобус, и все же она закончила sh свое путешествие ко дню D?

Гарантируется, что Бакет сможет завершить sh свое путешествие ко дню D.

Ввод:

В первой строке входных данных указывается количество тестовых случаев, за которыми следуют T. Каждый тестовый пример начинается со строки, содержащей два целых числа N и D. Затем следует еще одна строка, содержащая N целых чисел, i-й - Xi.

Выходные данные:

Для каждого тестового примера выведите одну строку, содержащую Case #x: y, где x - номер тестового набора (начиная с 1), а y - последний день, когда она могла взять первую шину, и все же окончание sh своего путешествия к дню D.

Пределы:

Предел времени: 10 секунд на тестовый набор. Ограничение памяти: 1 ГБ. 1 ≤ T ≤ 100. 1 ≤ Xi ≤ D. 1 ≤ N ≤ 1000. Гарантируется, что Бакет сможет завершить свой sh путь до дня D.

Образец:

Ввод ->

3

3 10

3 7 2

4 100

11 10 5 50

1 1

1

Выход ->

Дело № 1: 6

Дело № 2: 99

Дело № 3: 1

Ниже представлен код, который я отправил: 

from sys import stdin
def busroute(arr,d,i):
    while i>=0:
        if d%arr[i]==0:
            i-=1
        else:
            d-=1
    return d

def main():
    t=int(stdin.readline())
    case=1
    for _ in xrange(t):
        n,d=map(int,stdin.readline().split())
        arr=list(map(int,stdin.readline().split()))
        d = busroute(arr,d,n-1)
        print("Case #{}: {}".format(case,d))
        case+=1

if __name__ == "__main__":
    main()
...