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

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

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

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

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

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

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

Пояснение

Решение:

Пусть $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\ge 1088$ . Рассмотрим все четыре случая.

$r=1$ : $4N+2\ge 1088\Rightarrow N\ge 272$ . Наименьшее число вида $4k+1$ — это $N=273$ .
$r=2$ : $16N+4\ge 1088\Rightarrow N\ge 68$ . Наименьшее число вида $4k+2$ — это $N=70$ , $R=1124$ .
$r=3$ : $16N+6\ge 1088\Rightarrow N\ge 68$ . Наименьшее число вида $4k+3$ — это $N=71$ , $R=1142$ .
$r=0$ : $N=64$ даёт $R=1024$ — мало; следующее кратное четырём $N=68$ даёт $R=16\cdot 68+4=1092\ge 1088$ — подходит.

Обратим внимание на «ловушку»: $N=66$ даёт $R=1060$ , а $N=67$ даёт $R=1078$ — оба меньше 1088. Наименьшее из чисел 273, 70, 71, 68 — это 68.

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(min(n for n in range(1, 1000) if alg(n) >= 1088))

Ответ: 68