Top.Mail.Ru
Ответы
Аватар пользователя
alik_aliev39
3г
Аватар пользователяПрограммирование

Вопрос по задаче с сайт acmp 996

Не понимаю как оптимизировать свой код, не проходит по времени, вот мой код:

Изображение

def range_array(number):

array = [1]

for i in range(1, number):

if i+1 in array:

array.append(array[i-1]+3)

else:

array.append(array[i - 1]+2)

return array


n = int(input())


print(range_array(n)[-1])

По дате
По рейтингу
Аватар пользователя
graf_planarnyi
Новичок
3г

очень просто: вместо того, чтобы вложенным циклом линейно проходить по всему содержимому массива на каждом шаге, тем самым усложняя решение до O(n^2), можно с помощью бинпоиска проверять есть ли текущее n_i в массиве или нет, сводя задачу к O(nlogn):

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051
 def check(x, arr):
 
    l, r = 0, len(arr) - 1
 
    while l <= r:
 
        m = (l + r) // 2
 
        if arr[m] > x:
 
            r = m - 1
 
        elif arr[m] < x:
 
            l = m + 1
 
        else:
 
            return True
 
    return False
 

 

 
def solve(n0):
 
    a = [1]
 
    while len(a) < n0:
 
        if check(len(a) + 1, a):
 
            a.append(a[-1] + 3)
 
        else:
 
            a.append(a[-1] + 2)
 
    print(a[-1])
 

 

 
n = int(input())
 
solve(n)