Решение перебором

Вернёмся к задаче темы: чётному N справа дописывается 10, нечётному — 01, нужно наименьшее N, для которого R > 150.

Программа перебирает N по порядку, для каждого буквально выполняет алгоритм и проверяет результат. Сначала убедимся, что алгоритм записан правильно: напечатаем результаты для маленьких N и сверим с примером из условия или с ручным счётом.

for n in range(1, 9):    s = bin(n)[2:]    if n % 2 == 0:        s = s + '10'    else:        s = s + '01'    r = int(s, 2)    print(n, r)

Проверка руками: 5 = 101, нечётное, дописываем 01 — 10101 = 21. Совпало. Теперь фильтруем по вопросу: печатаем первое N, для которого R > 150, и останавливаем цикл.

for n in range(1, 200):    s = bin(n)[2:]    if n % 2 == 0:        s = s + '10'    else:        s = s + '01'    r = int(s, 2)    if r > 150:        print(n, r)        break

Ответ — 38. Первое найденное N действительно наименьшее: все меньшие уже проверены. Дальше разберём, когда так остановиться нельзя и как выбрать границу перебора.

Сначала пойми, что именно ищут: наименьшее N, наименьшее R или что-то ещё. В задании могут попросить разные вещи. Проверка во всех случаях — буквальный перевод условия, а выбирают и выводят разное. Выбери формулировку:

наименьшее N, для которого R > T

проверяем R > Tвыбираем минимальное N

наибольшее N, для которого R ≤ T

проверяем R ≤ Tвыбираем максимальное N

наименьшее возможное R > T

проверяем R > Tвыбираем минимальное R

наибольшее возможное R ≤ T

проверяем R ≤ Tвыбираем максимальное R

N, при котором R минимально среди R > T

проверяем R > Tсначала минимизируем R, затем выводим соответствующее N

Последний вариант особенно важен. Рассмотрим учебный алгоритм: если N чётное, справа дописать 111; если нечётное — дописать 0. Чётные N дают большие результаты, нечётные — маленькие.

Пусть требуется R > 8. Тогда минимальное подходящее N равно 2, поскольку оно даёт R = 23; минимальное подходящее R равно 10, оно получается при N = 5.

Почему минимальный результат именно 10? Число 9 получить нельзя: нечётные N дают чётные результаты, а чётные N ≥ 2 дают результаты не меньше 23.

Это пример того, что при увеличении N результат может уменьшаться.

Поэтому для наименьшего R программа не останавливается на первом подходящем N, а проверяет все входы и запоминает лучший результат и вход, на котором он получен. Запусти программу по шагам: best_r сначала станет 23 при N = 2, а потом уменьшится до 10 при N = 5.

best_n = 0best_r = 1000for n in range(2, 6):    r = 2 * n    if n % 2 == 0:        r = 8 * n + 7    if r > 8 and r < best_r:        best_n = n        best_r = rprint(best_n, best_r)

Начальное значение 1000 заведомо больше любого результата здесь, поэтому первый подходящий R его заменит. Перебор начат с 2, потому что N = 1 даёт R = 2 — оно не больше 8. Граница 6 в range пока взята для примера; как выбирать её честно, разберём ниже.

Остановить перебор на первом подходящем числе можно, только если понятно, почему оно лучшее. Команда break завершает ближайший цикл. Если мы перебираем N = 1, 2, 3, … и ищем минимальное N, то первый подходящий вариант действительно минимален: все меньшие уже проверены. Зависимость R от N при этом может быть любой.

Но если ищем минимальное R, первый подходящий вход не обязательно даст лучший результат. Это показал предыдущий пример.

Остановиться на первом подходящем N и для наименьшего R можно, когда справа всегда дописывается одинаковое число цифр, а исходная запись сохраняется: тогда больший вход всегда даёт больший результат.

Где остановить перебор, подсказывает сама задача, а не привычка писать range(1, 1000). Перебор — это проверка всех кандидатов подряд. Он даёт обоснованный ответ, если выполнены два условия:

1. каждый кандидат обрабатывается точно по алгоритму;
2. все кандидаты, способные повлиять на ответ, входят в диапазон.

Главный случай: алгоритм только дописывает цифры, сохраняя исходную запись. Тогда R ≥ N. Пусть ищем минимальное подходящее R и уже нашли какой-то результат R₀. Любой результат лучше него будет не больше R₀. Значит, для такого результата N ≤ R ≤ R₀. Поэтому все входы N > R₀ можно исключить. Это даёт строгую границу даже без знания окончательного ответа.

При удалении цифр, инверсии или замене начала записи неравенство R ≥ N может быть неверным. Его нельзя использовать автоматически.

Теперь полностью решим задачу с двумя последовательными проверками суммы цифр. Учебное условие:

1. получить двоичную запись N;
2. справа дописать остаток от деления суммы её цифр на 2;
3. повторить действие для новой записи;
4. найти минимальное N, для которого R > 100.

Хвост здесь всегда 00 или 10, то есть R = 4N или R = 4N + 2 (подтема 3). Следовательно, R ≤ 4N + 2. Если N ≤ 24, то R ≤ 4 · 24 + 2 = 98. Поэтому все N ≤ 24 точно не подходят.

Проверим 25: 25₁₀ = 11001₂. В записи три единицы — нечётное количество. Значит, дописывается 10: 11001 → 1100110, R = 4 · 25 + 2 = 102. Условие выполнено: 102 > 100. Следовательно, N_min = 25. Здесь мы не просто нашли подходящее число, но и доказали, что меньших нет.

Программа, буквально повторяющая условие:

def transform_binary(n):    s = bin(n)[2:]     remainder = s.count('1') % 2    s = s + str(remainder)     remainder = s.count('1') % 2    s = s + str(remainder)     return int(s, 2)  for n in range(1, 27):    r = transform_binary(n)     if r > 100:        print(n)        break

range(1, 27) задаёт числа от 1 до 26 включительно: правая граница в range не входит. Почему диапазона достаточно? При N = 26: R ≥ 4 · 26 = 104 > 100. То есть хотя бы один подходящий вход гарантированно встретится не позднее 26.

Если бы вопрос был о минимальном R > 100, ответом было бы 102. Здесь это следует и из доказанного роста R вместе с N: справа всегда дописываются ровно две цифры.

Если результат задан, программа ищет вход, при котором он получается; разные результаты удобно собирать в множество. Обратный ход удобен руками, но программе проще пройти по входам и сравнить результат с заданным. Граница перебора берётся из того же рассуждения: алгоритм только дописывает цифры, значит R ≥ N, и входы больше R проверять не нужно.

Когда спрашивают количество различных результатов, одинаковые значения R, полученные от разных входов, учитывают один раз. Их удобно складывать в множество: оно хранит значения без повторов.

results = set()for n in range(1, 103):    r = transform_binary(n)    results.add(r)    if r == 102:        print(n) print(100 in results, len(results))

Вход для 102 — это 25; число 100 не получается ни из одного входа. Различных результатов 102 — столько же, сколько входов: при дописывании ровно двух цифр разные N дают разные R. Для алгоритма, который отбрасывает цифры, это уже не так.

Разберём троичный алгоритм, в котором длина дописываемого блока меняется. Учебное условие:

1. построить троичную запись N;
2. если N делится на 3, дописать справа две последние цифры этой записи;
3. иначе остаток от деления N на 3 умножить на 7, перевести произведение в троичную систему и дописать справа;
4. найти максимальное R, не превышающее 300.

Разделим все входы по остатку от деления на 3. Если остаток равен 0, дописываются две последние цифры: R = 9N + (N mod 9). Если остаток равен 1: 1 · 7 = 7 = 21₃, дописали две цифры, R = 9N + 7. Если остаток равен 2: 2 · 7 = 14 = 112₃, дописали уже три цифры, R = 27N + 14.

Например, N = 2 даёт R = 68, а N = 3 — R = 30. Результат уменьшился при увеличении входа. Поэтому нельзя остановиться, впервые получив значение больше 300, и считать дальнейший поиск бесполезным.

Но можно строго ограничить входы. Во всех ветвях дописывается не меньше двух троичных цифр: R ≥ 9N. При R ≤ 300 получаем N ≤ 33.

Программа перебирает N от 1 до 33 и запоминает наибольший подходящий результат; она использует функцию to_base:

def transform_ternary(n):    s = to_base(n, 3)     if n % 3 == 0:        s = s + s[-2:]    else:        extra = (n % 3) * 7        s = s + to_base(extra, 3)     return int(s, 3)  best_r = -1 for n in range(1, 34):    r = transform_ternary(n)     if r <= 300:        if r > best_r:            best_r = r print(best_r)

best_r хранит лучший результат среди уже проверенных. Начальное значение -1 выбрано потому, что все возможные результаты неотрицательны. Поэтому первый подходящий результат окажется больше него. Мы сравниваем именно r, поскольку вопрос требует максимальное выходное число.

• Шаблонцикл по N, алгоритм буквально, сверка с примером, фильтр по вопросу
• Наименьшее Nпервое подходящее при переборе по возрастанию
• Наименьшее Rперебрать всё и хранить лучший R и его N
• Границаалгоритм только дописывает цифры — R ≥ N
• Задан Rпроверка равенства; различные результаты — множество