Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Prokop1
Приказчик Прокопий вёл учёт в лавке купца Пятипузова. Считал Прокопий отлично, а вот записывать числа ему было непросто: после Гангутского сражения (Прокопий-то моряком раньше был), мог он обрубком правой руки писать только нолики и единички. Про двоичную систему Прокопий не знал, но придумал собственный способ записи чисел. Представлял он число в виде суммы чисел, состоящих только из единиц и нулей. К примеру, число 1714 (год того самого сражения при Гангуте) он иногда представлял как 1111 + 101 + 101 + 101 + 100 + 100 + 100, а иногда как 1101 + 111 + 101 + 101 + 100 + 100 + 100, но всегда слагаемых было минимальное возможное количество и шли они в порядке невозрастания. Плюсиков Прокопий, естественно, не писал, оставлял вместо них пробелы.
Разработайте программу, которая получает на вход натуральное число N и подсчитывает количество способов представить его в системе Прокопия. Напомним: Прокопий представлял число как сумму.
Входные данные. Натуральное число, не превышающее 99999.
Выходные данные. натуральное число – количество способов представления введённого числа в системе Прокопия.
Для отправки решений необходимо выполнить вход.
|