Как уложиться в лимиты задачи?
Решил на днях порешать задачи на одном сайте. Для данной задачи установлены лимиты в использовании 256 мегабайт памяти и не более 1 секунды на исполнение кода.
Задача звучит так:
У старика есть бесконечное количество зелёных, красных и жёлтых яблок.
Он решил ставить яблоки в ряд по такому алгоритму: сначала g зелёных яблок, потом y жёлтых яблок, далее r красных яблок, y жёлтых яблок, и наконец g зелёных яблок (то есть, если g=1, y=3, r=4, то ряд будет выглядеть так: GYYYRRRRYYYG).
Цель задачи - найти цвет яблока на n-ной позиции.
Входные данные:
n, g, y, r (1≤n,g,y,r≤10^12)
Всё бы ничего, но при проверке, в одном из своих тестов сайт в качестве n использует число 1000000000000.
Собственно это и доставляет проблему - при выполнении моего кода с небольшими числами всё окей, но стоит вписать триллион и пайтон намертво виснет. Подскажите, есть ли возможность оптимизировать программу?
Код:
n, g, y, r = map(int, input().split())
k = ""
x = ""
x += "G"*g
x += "Y"*y
x += "R"*r
x += "Y"*y
x += "G"*g
while not len(k)>n:
k += x
print(k[n-1])
Ответы (2 шт):
Не стоит заводить эту последовательность в виде строки, задачу нужно решать математически.
Очевидно, что вся последовательность повторяется блоками по (g+y+r)+(y+g) яблок.
Тогда алгоритм примерно следующий:
Делим
nбез остатка на длину повторяющегося блока, тем самым определяя количество блоков, которые мы можем без ущерба отбросить.Внутри уже оставшейся части одного блока определяем позицию яблока, сделать это просто, так как каждый блок разделён на 5 частей:
[0 .. g-1, g .. g+y-1, ... , (g+y+r)+(y+g)-1
Наша задача лишь определить к какой из 5 частей относится число n
- Вывести цвет яблока, который соответствует части, в которую попало число
n
Подскажите, есть ли возможность оптимизировать программу?
здесь нет смысла создавать строку длиной n, можно ограничиться только одним сегментом, далее взять остаток от деления n на длину сегмента:
k = 'g'*g + 'y'*y + 'r'*r + 'y'*y + 'g'*g
print(k[n%len(k)-1])