ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1131. Копирование

time limit on python 3 HELP PLEASE I GIVE MONEY
Послано ivan228 17 окт 2018 22:34
import sys
n,k=map(int,input().split())
ans=0
nn=1
on=1
if n==1:
    print(0)
    sys.exit()
for i in range(100000000000000000000):
    if on<=k:
        nn+=on
        on+=on
        ans+=1
    elif k<n:
        nn+=k
        on+=k
        ans+=1
    if nn>=n:
        print(ans)
        sys.exit()
i can not understand why optimization my cod
if i got ac with you help i give you 1000 rubles

Edited by author 17.10.2018 22:35
Re: time limit on python 3 HELP PLEASE I GIVE MONEY
Послано Ivan Avdonin (Vologda ML, MSU) 13 фев 2020 06:12
The reason why you got time limit is that you don't use optimal algorithm. Your algorithm can be even correct, but to pass you need downgrade your algorithm. Maybe you could find some formula that would describe the whole process. Python is not the case here. You would get the same time limit issue with C.

I launched your script with N = 10000000 and K = 2 and it took 1.833s on my machine to get the correct answer when the time limit is 0.25s. Of course it will grow up nonlinearly with bigger N. So it would take ages with N = 10^9 (the edge value).

$ time echo "10000000 2" | python 1131_bruteforce.py

real    0m1.833s
user    0m1.824s
sys     0m0.007s

ivan228 писал(a) 17 октября 2018 22:34
if i got ac with you help i give you 1000 rubles
Edited by author 17.10.2018 22:35

P.S. I don't need your money if you finally solve it :)

Edited by author 13.02.2020 06:12

Edited by author 13.02.2020 06:12