Задача №1339. Цифры и числа
Как много открытий можно сделать, исследуя числа и составляющие их цифры!
Петя очень любит арифметику, и кроме домашних заданий он постоянно придумывает дополнительные задачи. Однажды он стал прибавлять к натуральным числам сумму составляющих их цифр. Петя обнаружил, что некоторые числа, например 20, не могут быть получены из других чисел в результате такого действия. Эти числа ему не понравились, и он назвал их некрасивыми.
Позже, когда Петя начал изучать информатику, те же исследования он стал проводить с натуральными числами в двоичной системе счисления. Например, двоичное число 11102 (в десятичной системе — 14) можно получить из числа 11002 (в десятичной системе — 12), прибавив к последнему сумму его цифр:
11002 + 102 = 11102.
Петя решил исследовать множество двоичных некрасивых чисел. Первые пять некрасивых чисел он нашел без труда: 1 = 12, 4 = 1002, 6 = 1102, 13 = 11012, 15 = 11112. Продолжить работу он собирается с помощью компьютера.
Требуется написать программу, которая определяет количество двоичных некрасивых чисел, не превосходящих заданного числа n.
В первой строке входного файла содержится число n, записанное в десятичной системе счисления (1 ≤ n ≤ 1018).
В единственной строке выходного файла должно содержаться единственное число — количество двоичных некрасивых чисел, не превосходящих n.
Примечание
Решения, корректно работающие при n ≤ 106, будут оцениваться из 40 баллов.
17
5
18
6