시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 15 | 0 | 0 | 0.000% |
Как много открытий можно сделать, исследуя числа и составляющие их цифры!
Петя очень любит арифметику, и кроме домашних заданий он постоянно придумывает дополнительные задачи. Однажды он стал прибавлять к натуральным числам сумму составляющих их цифр. Петя обнаружил, что некоторые числа, например 20, не могут быть получены из других чисел в результате такого действия. Эти числа ему не понравились, и он назвал их некрасивыми.
Позже, когда Петя начал изучать информатику, те же исследования он стал проводить с натуральными числами в двоичной системе счисления. Например, двоичное число 11102 (в десятичной системе — 14) можно получить из числа 11002 (в десятичной системе — 12), прибавив к последнему сумму его цифр:
11002 + 102 = 11102.
Петя решил исследовать множество двоичных некрасивых чисел. Первые пять некрасивых чисел он нашел без труда: 1 = 12, 4 = 1002, 6 = 1102, 13 = 11012, 15 = 11112. Продолжить работу он собирается с помощью компьютера.
Требуется написать программу, которая определяет количество двоичных некрасивых чисел, не превосходящих заданного числа n.
В первой строке входного файла содержится число n, записанное в десятичной системе счисления (1 ≤ n ≤ 1018).
В единственной строке выходного файла должно содержаться единственное число — количество двоичных некрасивых чисел, не превосходящих n.
1
1
13
4
14
4