Python задача "Игра с числами"

Решение:

Сначала разбиваем результирующее число на пары соседних цифр, считая первую и последнюю цифры отдельно. Затем для каждой пары проверяем возможные варианты суммирования и запоминаем их в отдельном списке.
Для каждой следующей пары будем проверять возможные комбинации суммирования, используя предыдущий список. После прохода через все пары, запоминаем весь список полученных возможных вариантов исходных чисел.
Затем нужно проверить каждый вариант исходного числа, возможный на основе результата игры. Для этого запускаем процесс обратного пересчёта числа, снова разбивая его на пары соседних цифр и складывая с учётом возможных суммирований. Если результат совпадает с заданным результирующим числом, то запоминаем исходное число.
В конце выводим количество найденных вариантов исходных чисел и сами эти числа.

 n = int(input()) # количество цифр в результирующем числе 

result = list(map(int, input())) # результирующее число 

comb = [[] for i in range(n)] # список возможных сумм для каждой пары цифр 

comb[0] = [[i] for i in range(10)] # инициализация для первой цифры 

 

for i in range(1, n-1): # перебираем пары цифр, начиная со второй 

    for c in comb[i-1]: # перебираем возможные суммы предыдущей пары 

        for j in range(max(0, 18-sum(c)), 10): # возможные значения второй цифры 

            if j < 10-sum(c): # если сумма двух цифр не превышает 9 

                comb[i].append(c+[j]) # добавляем возможную сумму 

            else: # если сумма двух цифр превышает 9 

                comb[i].append(c+[j%10]) # добавляем последнюю цифру возможной суммы 

 

for c in comb[n-2]: # перебираем возможные суммы последней пары 

    if sum(c) % 10 == result[n-1]: # если сумма равна последней цифре результирующего числа 

        num = [0]*(n-1) + [c[-1]] # начинаем обратный пересчёт с последней цифры 

        for i in range(n-2, 0, -1): # перебираем пары цифр в обратном порядке 

            val = -1 

            for j in range(10): # перебираем возможные цифры первой пары 

                if j + num[i+1] in comb[i-1][c[i-1]]: # если такая сумма возможна 

                    val = j 

                    break 

            if val == -1: # если не найдено подходящей цифры, выходим из цикла 

                break 

            num[i] = val 

        else: 

            print(1) # если вариант числа подходит, выводим его 

            print("".join(map(str, num))) 

            break 

else: 

    nums = [] # список найденных вариантов чисел 

    for c in comb[n-2]: # перебираем возможные суммы последней пары 

        if sum(c) % 10 == result[n-1]: # если сумма равна последней цифре результирующего числа 

            num = [0]*(n-1) + [c[-1]] # начинаем обратный пересчёт с последней цифры 

            for i in range(n-2, 0, -1): # перебираем пары цифр в обратном порядке 

                val = -1 

                for j in range(10): # перебираем возможные цифры первой пары 

                    if j + num[i+1] in comb[i-1][c[i-1]]: # если такая сумма возможна 

                        val = j 

                        break 

                if val == -1: # если не найдено подходящей цифры, выходим из цикла 

                    break 

                num[i] = val 

            else: 

                nums.append(num) # если вариант числа подходит, добавляем его в список 

    print(len(nums)) # выводим количество найденных вариантов 

    for num in nums: 

        print("".join(map(str, num))) # выводим все варианты чисел 

 5 

59237 

Traceback (most recent call last): 

  File "C:\Users\User\Desktop\pythonProject\7.py", line 22, in  

    if j + num[i + 1] in comb[i - 1][c[i - 1]]:  # если такая сумма возможна 

IndexError: list index out of range 

Рассмотрим обратный порядок действий, которые выполняет Миша, чтобы получить результирующее число. Пусть дано число $x_1 x_2 \ldots x_n$ и получено число $y_1 y_2 \ldots y_k$ ($k < n$). Тогда последняя цифра числа $y$ равна $(x_{k-1} + x_n)\text{ mod } 10$ (если $k = 1$, то $y_1 = x_n$), а первая цифра равна $(x_1 + x_{k+1})\text{ mod } 10$.

Заметим, что при восстановлении исходного числа сохраняется количество цифр, а также последняя цифра исходного числа совпадает с последней цифрой результирующего числа. Также имеем следующее соотношение:

$$
x_k = (y_{k-1} + x_{n})\text{ mod } 10
$$

Теперь мы можем последовательно восстанавливать все цифры исходного числа, начиная от последней, и использовать соотношение выше. Если для какой-то из цифр будет несколько возможных значений, то мы можем соответствующим образом изменить значения уже восстановленных цифр. Затем нужно проверить, что полученное число действительно соответствует результирующему. Если это так, то мы можем добавить исходное число в ответ.

Количество возможных вариантов исходного числа не превосходит $10^n$ (так как каждая цифра может быть любой из $0$, $1$, $\dots$, $9$). Это число достаточно большое, поэтому нам нужно восстановить исходное число эффективно. Можно заметить, что в вычислениях используются только $x_{n-1}$, $x_n$, $y_{k-1}$ и $k$. Поэтому мы можем перебирать только эти значения и вычислять значение последней цифры исходного числа ($x_{k-1}$), а затем последовательно восстанавливать все остальные цифры.

Итого, временная сложность алгоритма составляет $O(n)$, что достигается при помощи двух проходов по строке.