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

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

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

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

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

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

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

Пояснение

Решение:

Пусть $r=N\bmod 4$ — последняя цифра четверичной записи $N$ . Разберём, что приписывается справа в каждом случае.

$r=0$ : приписываются две последние четверичные цифры, то есть запись удлиняется на два разряда, а приписанное значение равно $N\bmod 16$ . Значит $R=16N+(N\bmod 16)$ .
$r=1$ : $2r=2=2_4$ — один разряд, поэтому $R=4N+2$ .
$r=2$ : $2r=4=10_4$ — два разряда, поэтому $R=16N+4$ .
$r=3$ : $2r=6=12_4$ — два разряда, поэтому $R=16N+6$ .

Сверим с примерами из условия: $N=11$ , $r=3$ , $R=16\cdot 11+6=182$ ; $N=12$ , $r=0$ , $R=16\cdot 12+12=204$ . Совпадает.

Ключевое наблюдение: только при $r=1$ число увеличивается в 4 раза, во всех остальных случаях — в 16 раз.

Нужно наибольшее $N$ , при котором $R\lt 369$ . Рассмотрим все четыре случая.

$r=1$ : $4N+2\lt 369\Rightarrow N\le 91$ . Наибольшее число вида $4k+1$ , не превосходящее 91, — это $N=89$ , для него $R=358$ .
$r=2$ : $16N+4\lt 369\Rightarrow N\le 22$ . Подходит $N=22$ , $R=356$ .
$r=3$ : $16N+6\lt 369\Rightarrow N\le 22$ . Наибольшее число вида $4k+3$ — это $N=19$ , $R=310$ .
$r=0$ : $16N\lt 369\Rightarrow N\le 23$ . Подходит $N=20$ , $R=16\cdot 20+4=324$ .

Наибольшее из чисел 89, 22, 19, 20 — это 89.

def alg(n):
    q = ''
    m = n
    while m:
        q = str(m % 4) + q
        m //= 4
    if n % 4 == 0:
        q += q[-2:]
    else:
        t = (n % 4) * 2
        q += str(t) if t < 4 else str(t // 4) + str(t % 4)
    return int(q, 4)

print(max(n for n in range(1, 1000) if alg(n) < 369))

Ответ: 89