Введем понятие "производного числа Y для числа X" - это число Y равное сумме числа X и сумме его цифр, например:
147 => 147 + 1 + 4 + 7 = 159. Производное число можно вычислить для любого неотрицательного числа.
Есть понятие "генератор числа X для числа Y" - это число X, сумма которого с его цифрами равна числу Y, например:
159 => 147. Генератор числа существует не для любого неотрицательного числа.
Те числа, для которых не существует числел генераторов называются "самопроизводными числами", например: 143. Таких чисел примерно на один порядок меньше.
Необходимо вывести на последовательности чисел от 0 до 10^9 признак является ли число самопроизводным (True) или генератором (False).
Ограничение по времени 1 сек, по памяти 16 Мб.
N: 10000000
P: 9022267
SP: 977796
P + SP: 10000063
Unique terms: {'2:1', '28:1', '15:1', '11:9', '54:1', '41:1', '11:5', '2:4', '11:7', '11:6', '11:8'}
Frequency dictionary: Counter({'2:1': 90000, '11:9': 80002, '11:8': 18000, '15:1': 9000, '11:7': 1800, '28:1': 900, '11:6': 180, '41:1': 90, '11:5': 18, '54:1': 9, '2:4': 2})
(2, 80002, 90000, 18000, 9000, 1800, 900, 180, 90, 18, 9)
18181.909090909092
Compress [6] str: kb9o9n9m8laiji9o9n9m8laiji9o9n9m8laiji9o9n9m8laiji9o9n9m8laiji9o9n9m8laiji9o9n9m8laiji9o9n9m8laiji9o9n9m8laiji9o9n9m9lk
{'2:1': 'a', '11:9': 'b', '11:8': 'c', '15:1': 'd', '11:7': 'e', '28:1': 'f', '11:6': 'g', '41:1': 'h', '11:5': 'i', '54:1': 'j', '2:4': 'k', 'ab': 'l', '8lacdc': 'm', '9m8laefe': 'n', '9n9m8laghg': 'o'}
10000060
[Finished in 18.8s]