Условие
Источник задания: kompege.ru — 10657
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:
- Строится троичная запись числа N.
- К этой записи дописываются разряды по следующему правилу. Если сумма троичных разрядов кратна 3, слева дописывается 20, иначе 10.
- Полученная таким образом запись является троичной записью искомого числа R.
Например, для числа 10 троичная запись 1013 преобразуется в запись 101013 = 91, для числа 11 троичная запись 1023 преобразуется в 201023 = 173.
Укажите максимальное значение N, после обработки которого с помощью этого алгоритма получается число R, меньшее чем 100.
Решение
Листинг программы
def v3(x):
r = ''
while x > 0:
r = str(x % 3) + r
x //= 3
return r
n_max = 0
for n in range(1, 100):
r = v3(n)
sum = 0
for j in r:
sum += int(j)
if sum % 3 == 0:
r = '20' + r
else:
r = '10' + r
r = int(r, 3)
if r < 100 and n > n_max:
n_max = n
print(n_max)