Не могу решить задание ЕГЭ. Почему мой код не работает?

Question

[drxnni]

Вот задание:

Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом:
1.  Строится двоичная запись числа N.
2.  Подсчитывается количество чётных и нечётных цифр в десятичной записи заданного числа. Если в десятичной записи больше чётных цифр, то в конец двоичной записи дописывается 1, если нечётных  — 0. Если чётных и нечётных цифр в десятичной записи поровну, то в конец двоичной записи дописывается 0, если данное число чётное, и 1  — если нечётное.
3−4.  Пункт 2 повторяется для вновь полученных чисел ещё два раза.
5.  Результатом работы алгоритма становится десятичная запись полученного числа R.
Определите количество принадлежащих отрезку [876 544; 1 234 567 899] чисел, которые могут получиться в результате работы этого алгоритма.

Вот мой код (пожалуйста, не убирайте метод replace, если это возможно):

res = []
for n in range(1, 10000):
    s = bin(n)[2:]
    for _ in range(3):
        i = str(n)
        i = i.replace('0', '2').replace('4', '2').replace('6', '2').replace('8', '2')
        i = i.replace('3', '1').replace('5', '1').replace('7', '1').replace('9', '1')
        if i.count('2') > i.count('1'):
            s += '1'
        elif i.count('2') < i.count('1'):
            s += '0'
        elif i.count('2') == i.count('1'):
            if i.count('2') % 2 == 0:
                s += '0'
            else:
                s += '1'
        

if int(s, 2) >= 876544 and int(s, 2) <= 1234567899:
    res.append(int(s, 2))
print(len(res))

Comments

[Антон Горецкий]

сделай нормальное форматирование кода питон. Сейчас это выглядит бесполезно.

[Алан Гибизов]

См. тут

[drxnni]

Алан Гибизов, спасибо за помощь! :)

[Алан Гибизов]

Очевидно, if int(s, 2) должен быть в теле цикла for

[Алан Гибизов]

Ну и есть у меня стойкое ощущение, что брутфорсом это решать неправильно. Первое, что приходит в голову, это проанализировать, что именно происходит при всех этих дописываниях, и подумать, что там к чему. Чую, там всё проще, чем выглядит.
Но, возможно, я не прав.

Answer 1

[Vindicar]

Тебе выше правильно намекнули.
Во-первых, нужно увидеть простую вещь: дописывание нуля в конец двоичного представления - это то же, что умножение на 2. Назовём это операция А. А дописывание единицы - то же, что умножение на 2 и прибавление 1. Назовём это операция Б. Таким образом, можно избавиться от двоичной системы в задании.

Второе: операция А будет давать в результате только чётные числа, независимо от аргумента. Аналогично, операция Б будет давать только нечётные числа, независимо от аргумента.

Третье: результат как операции А, так и операции Б всегда больше аргумента. Более того, больший аргумент даёт больший результат. Это легко показать.
Пусть у нас есть число x. Результат операции A меньше, чем операции Б над тем же числом, поэтому мы должны проверить только один сценарий: когда к x применяется операция А, а к x - 1 - операция Б. Значит, x станет 2 * x, а x - 1 станет 2 * (x - 1) + 1 = 2 * x - 1. Т.е. для x - 1 результат меньше. Т.е. даже в таком, самом спорном случае, меньшее число даёт меньший результат

Четвёртое: задачу можно решать задом наперёд. У нас есть целевые числа - значит, мы должны применить к ним алгоритм наоборот, чтобы получить исходные. Это и даст нам диапазон для поиска исходных чисел.

Дальше уже проще. Смотрим на начало целевого диапазона, число 876 544. Оно чётное, значит, оно могло быть создано только операцией А. Значит, чтобы получить исходное число, нужно поделить его на 2. 876 544 / 2 = 438 272. Это число тоже чётное, оно тоже могло быть создано только операцией А. 438 272/ 2 = 219 136. Оно тоже чётное. Значит, третий раз применяем операцию А наоборот: 219 136 / 2 = 109 568. Исходя из пункта 3, можем сказать, что числа, меньше 109 568, не могут дать результат, больший или равный 876 544.

Аналогично анализируем верхнюю границу целевого диапазона.
1 234 567 899 = 2 * 617 283 949 + 1 (операция Б)
617 283 949 = 2 * 308 641 974 + 1 (операция Б)
308 641 974 = 2 * 154 320 987 (операция А)
Значит, исходное число должно быть не более 154 320 987. Вот тебе и диапазон для поиска.
А поскольку большие аргументы дают большие результаты, то это означает, что ни одно число меньше 154 320 987 не даст результат, который выйдет за верхнюю границу диапазона (1 234 567 899). Т.е. искомые числа - это весь диапазон от 109 568 до 154 320 987. Посчитать, сколько чисел в диапазоне, тривиально.

Answer 2

[chupasaurus]

Потому что 876544 / 8 = 109568. Любая математическая задача начинается с расчёта областей определения и значения.