от MemoryError спасёт xrange. А в остальном пост не читал.

Спасибо. Но по времени все-равно жопа.

АВРПЛЫДАПВРЛЫА?

Что с тобой?

Сколько тебе лет?

Сколько тебе лет?

14

Тут не надо перебирать все числа.

Дам подсказку: если в некой совокупности чисел все числа в троичной записи имею одинаковую длинну, то лексикографически найменьшее здесь является минимальным и в традиционном смысле.

в лексикографическом порядке пойдут 0,1 ,10, 100...

тебе нужно взять меньшее из 1 и первого нацело делимого на 3 (в зависимости от того, что попадает в диапазон). Если таких нет, значит диапазон состоит из 2 чисел. Вот и вся задача.

> тебе нужно взять меньшее из 1 и первого нацело делимого на 3 (в зависимости от того, что попадает в диапазон). Если таких нет, значит диапазон состоит из 2 чисел. Вот и вся задача.

Дано:

11,12,20,21,22,100,101,102,110

Берём 11 и 20, наименшьее - 11

Правильный ответ должен быть 100

ах точно, про двоечки забыл

негоже сообщения свои удалять

логарифмы проходили же?

Можно попробовать решить так (не ручаюсь за корректность):

1) пусть есть интервал чисел от A_0 до A_n

2) Считаем l' = log_3 A_0, ' = 3 ** (ceiling l'), где log_3 - логарифм по основанию 3, а ceiling - округление вверх

3) Если A_0 ≤ l ≤ A_n - то ответ l, иначе ответ A_0

логарифмы проходили же?

Нет :( Но что это есть я посмотрел и применял в задаче.

l' = log_3 A_0, ' = 3 ** (ceiling l')

Такой синтаксис не понимаю.

l' = math.log(A_0, 3), l = 3 ** math.ceil( l' )

Заместо l' напиши любую переменную

Вот что у меня пока

import math
(s, e) = raw_input ().split ()

def rescale (num, n, i=10): #переводит из системы i (или десятичной) в систему n, (c)
	n = int (n)
	r = int (str (num), i)
	if n == 10: return r
	elif n == 2: return bin (r)[2:]
	elif n == 16: return hex (r)[2:]
	elif n == 8: return oct (r)[2:]
	else:
		p = ""
		while r>1:
			p = str (r%n) + p
			r = r/n
		if r == 0: return p
		elif r < 1: return p + str (r)
		else: return "1"+p


mins = []
s = int (s)
e = int (e)

for i in xrange (int (math.log (s, 3)), int (math.log (e, 3)) + 1):
	if 3**i >= s: mins += [3**i]
	else:
		mins += [min (range (s, 3**(i+1)))]

print int (min (sorted ([rescale (n, 3) for n in mins])), 3)

Программа работает неверно, а у меня уже мозги плывут.

Сработало. Все верно. Спасибо.
Теперь буду думать что это значит.

А ты напечатай табличку - первый столбик числа в троичной системе от 1 до 1000, второй столбик - логарифм по основаниею 3, третий столбик - количество цифр в троичном числе, четвёртый - ceil (log (x, 3) ), пятый 3 ** ceil (log (x, 3))

Прежде чем говорить, что всё работает - проверь на больших интервалах, где первое число уже и есть ответ

пятый столбик печатай в троичном виде

Прежде чем говорить, что всё работает - проверь на больших интервалах, где первое число уже и есть ответ

Дык у них там на сервере олимпиады все проверилось...

лорчую

Что это? Я C не знаю и даже не понимаю почти. А задачу мы решили.

Это вот что. Если в заданный интервал попадает число вида 3^k, то найменьшее из них и есть ответ. Если не попадает, то A - ответ.

Waterlaz

Если в заданный интервал попадает число вида 3^k, то найменьшее из них и есть ответ. Если не попадает, то A - ответ.

Почти то же самое написал раньше.

Но работающее решение мы уже нашли:

import math
(s, e) = raw_input ().split ()

mins = []
s = int (s)
e = int (e)

l = math.log(s, 3)
l = 3 ** math.ceil (l)

if s<=l<=e: print int(l)
else: print s

Раньше у тебя говно написано, а твое работающее решение - это как раз то, о чем я писал

Ну а C то тут причем?!

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

P.S. Участник заочной олимпиады 2006-2009 годов.

Я с тобой согласен, но таки очень уж интересно было. Тем более логарифмы в 9-м классе не изучал еще никто, так что честно все...

>Я с тобой согласен, но таки очень уж интересно было. Тем более логарифмы в 9-м классе не изучал еще никто, так что честно все...

Она и без логарифмов решается

Но как до такого решения додуматься-то?

def lexmin(start, end, base=3):
    value = 1
    while value <= end:
        if value >= start:
            return value
        value *= base
    return start

s, e = map(int, raw_input().split())
print lexmin(s, e)

C++ там был при том, что я переключился на него после того, как мои первые питоно-попытки тормозили. Потом было лень переключаться обратно, ибо питоно-версия ничем в плане алгоритма не отличается.

Про использование логарифмов я не догадался. Да и вообще, по большей части опытным путем нашел решение.
Я написал готовую тормозную реализация, после чего с ее помощью смотрел на то, как входные данные соотносятся с ответом.
Сначала я заметил, что числа делящиеся нацело на три меньше остальных, но это было ошибочное замечание, как показал опыт.
Потом я таки пришел к нужному факту, степени тройки всегда меньше, чем остальные числа из диапазона.
Основываясь на этом, я сделал отдельный случай, когда в диапазон попадают степени тройки, в противном случае использовалась тормозная реализация.
И все бы хорошо, но на больших значениях диапазона, в который не попадают степени тройки, все равно было недостаточно быстро (и памяти не хватало).
Пришлось смотреть на входные и выходные данные дальше.
Через какое-то время я заметил, что вектор с числами в троичном представлении, который ищет минимальное число с помощью сортировки, остается таким же как и был до этой самой сортировки.
Я проверил это наблюдение, и так и оказалось, числа между степенями тройки уже отсортированы.

Если бы у меня были листок бумаги, ручка и свет в комнате, я бы наверное быстрее догадался до решения =)

import math
def f(a):
    o=«»
    while True:
        k=a%3
        o=«012»[k]+o
        a=a/3
        if a==0:break
    return o 

(s,e)= raw_input().split()
if s==0:
    print 0;
    sys.exit();

a,b=f(int(s)),f(int(e))
#print a,b
if len(a)==len(b):
    print s
else:
    o=3**(len(a)-1)
    #print s,o
    if o<int(s):o=3**len(a)
    print o
 

>