Задание №5 — Анализ простейших алгоритмов

#69656Задание №5ФИПИ

Анализ алгоритмов и исполнители

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:

1) Строится четверичная запись числа N.
2) Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 4, то к этой записи дописываются две последние четверичные цифры;
б) если число N на 4 не делится, то остаток от деления умножается на 2, переводится в четверичную запись и дописывается в конец числа.

Полученная таким образом запись является четверичной записью искомого числа R.

Например, для исходного числа 11 = 23₄ результатом является число 2312₄ = 182, а для исходного числа 12 = 30₄ это число 3030₄ = 204.
Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число R, меньшее 261.

Правильный ответ

Пояснение

Решение:

Приписывание цифр справа — это умножение на степень четвёрки. Разберём, сколько цифр приписывается в каждом случае. Если $N$ делится на 4, приписываются сразу две цифры, и $R$ примерно в 16 раз больше $N$ . Если остаток равен 2 или 3, то удвоенный остаток равен $4 = 10_4$ или $6 = 12_4$ — это тоже две цифры, и снова $R \approx 16N$ . И только при остатке 1 удвоенный остаток равен $2 = 2_4$ — одна цифра, поэтому $R = 4N + 2$ .

Нам нужно $R \lt 261$ , то есть $R$ — маленькое, значит выгоден только случай с остатком 1. Из $4N + 2 \lt 261$ получаем $N \le 64$ , а вместе с условием $N \bmod 4 = 1$ наибольшее такое $N$ равно 61.

Проверка: $61 = 331_4$ , остаток $61 \bmod 4 = 1$ , удвоенный остаток $2 = 2_4$ , поэтому $R = 3312_4 = 3 \cdot 64 + 3 \cdot 16 + 1 \cdot 4 + 2 = 246 \lt 261$ . Все числа $N \gt 61$ дают больший результат: 62, 63 и 64 удлиняют запись на две цифры (получается $R$ порядка тысячи), а следующий «дешёвый» кандидат $N = 65 = 1001_4$ даёт $10012_4 = 262$ , что уже не меньше 261.

def to4(n):
    s = ''
    while n:
        s = str(n % 4) + s
        n //= 4
    return s or '0'

def R(N):
    q = to4(N)
    q += q[-2:] if N % 4 == 0 else to4(2 * (N % 4))
    return int(q, 4)

print(max(N for N in range(1, 1000) if R(N) < 261))   # 61

Ответ: 61