Да
разгледаме цяло
положително
число N. Има
различни
начини за
представянето
на N като
сума от
степени на
числото 3.
Например за
числото 10, има 5 разбивания:
1+1+1+1+1+1+1+1+1+1
1+1+1+1+1+1+1+3
1+1+1+1+3+3
1+3+3+3
1+9
Задача
Напишете програма, която определя броя на разбиванията на цяло положително число N като сума от степени на 3.
Вход
Входният файл sume3.in съдържа на първия ред цялото положително число N.
Изход
Изходният файл sume3.out трябва да съдържа единствен ред, на който е записан броя на представянията на числото N като сума от степени на числото 3. Ако намереното число е по-голямо или равно на 1000000000, да се изведат само последните 9 цифри на резултата.
Ограничения
Пример
sume3.in |
sume3.out |
10 |
5 |
Ограничение за време: 0.2 секунди на тест
prof. Dana Lica
"I. L. Caragiale" National College, Ploieşti
Contact:danal182001@yahoo.com
Превод
на български:
Стоян Капралов