Consideram
un numar natural N. Exista mai
multe modalitati de descompunere a acestuia ca suma de puteri ale lui 3.
De exemplu, pentru numarul 10,
exista 5 modalitati de descompunere:
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
Cerinta
Scrieti un program care sa determine numarul de descompuneri ale unui numar natural N ca suma de puteri ale lui 3.
Date de intrare
Fisierul de intrare sume3.in contine pe prima linie numarul natural N.
Date de iesire
Fisierul de iesire sume3.out va contine o singura linie pe care se va scrie numarul de descompuneri ale lui N ca suma de puteri ale lui 3. Daca numarul obtinut este mai mare sau egal cu 1000000000 afisati doar ultimele 9 cifre ale numarului.
Restrictii si precizari
| sume3.in | sume3.out |
|
10 |
5 |
Timp maxim de executie/test: 0.2 secunde
prof. Dana
Lica
C. N. "I.L.
Caragiale" Ploiesti
Contact:danal182001@yahoo.com