Алгоритм построения числа
В заданиях 5 из числа $N$ строят новое число по правилам: переводят в двоичную запись, дописывают биты, снова переводят в десятичную. Нужно найти наименьшее или наибольшее $N$ с заданным результатом.
Пример. К двоичной записи $N$ справа дописывают 0, если число единиц чётно, иначе 1; операцию повторяют дважды к получающейся записи. Результат — двоичная запись числа $R$. При каком наименьшем $N$ получится $R > 40$?
$N=10 = 1010_2$: единиц две (чётно) → $10100$; единиц две → $101000_2 = 40$, не подходит. $N=11 = 1011_2$: единиц три → $10111$; единиц четыре → $101110_2 = 46 > 40$. Ответ: 11.
for N in range(1, 1000) — построить строку, вычислить $R$, вывести первое подходящее. Но на бумаге тоже быстро: увеличивайте $N$ и следите за длиной записи.Исполнители: Редактор, Калькулятор, Чертёжник
Редактор заменяет подстроки: заменить(v, w) меняет первое слева вхождение $v$ на $w$; нашлось(v) проверяет наличие. Выполняйте замены буквально, каждый раз пересматривая строку заново.
Пример. Строка из 63 единиц. Программа: пока нашлось(111) заменить(111, 2). Что получится?
Каждая замена уменьшает длину на 2 и не создаёт новых «111»: из 63 единиц получится 21 двойка: 222…2.
Калькулятор имеет команды вроде «+1», «+3», «×2». Задача «сколько программ переводят число $a$ в $b$» решается таблицей:
Если есть требование «траектория содержит число $m$», ответ — $K(a \to m)\cdot K(m \to b)$.
Проверь себя. Команды «+2» и «×3». Сколько программ переводят число 2 в число 20?
Ответ: 5
Игры: выигрышные и проигрышные позиции
Двое ходят по очереди; в куче $S$ камней; ходы: «+1», «+3», «×2»; побеждает тот, после чьего хода в куче станет не меньше 40 камней. Позиции классифицируют:
- Выигрышная — есть ход, после которого выиграет ходящий (сразу или потому, что соперник окажется в проигрышной позиции).
- Проигрышная — любой ход даёт сопернику выигрышную позицию.
Позиции $S \ge 20$ выигрышны за один ход: $S\cdot 2 \ge 40$. Значит, если после хода Пети куча $\ge 20$ — Ваня выигрывает первым ходом. Проигрышная для ходящего позиция $S=19$: любой из ходов даёт 20, 22 или 38 — Ваня побеждает следующим ходом.