TopCoder

Thumb tumblr m6532itd121rnos1s
$(pr)^3pony$
https://prprprpony.github.io/blog/ $\\\huge PinkiePie:"OkieDokieLokie"$

User's AC Ratio

95.0% (57/60)

Submission's AC Ratio

63.3% (100/158)

Tags

Description

有一天球主在打開了一包多力多滋, 看到裡面有一張紙,寫著:

"恭喜您種了大獎, 獎品為兩個有趣的函式, 請用 dev-c++ 編譯並執行, 你就會覺得很開心!!!"

int g(int x) {
if(x%3==0) return 1+g(x/3);
else return 0;
}

int f(int x) {
if(x<=0) return 0;
return g(x)+f(x-1);
}

球主覺得這真是一個大爛獎就生氣地把這張紙給丟了。
不過事後他有點後悔, 他很好奇如果真的按找指示執行了這兩個函式, 會有什麼有趣的結果。

請你幫幫球主吧。給你一個數字 N, 請算出 f(N) 的結果
( 也就是 printf("%d",f(N)); )

Input Format

輸入有多組測試資料,每一組測資有一個整數 N。

1 <= N <= 500000000

注意:N 的範圍非常大 (可以到500,000,000),
如果直接把函式打在程式碼執行就上傳,一定會 TLE 喔..

Output Format

請印出 f(N) 的結果。

Sample Input

5
6
9

Sample Output

1
2
4

Hints

Problem Source

原TIOJ1703 / kelvin

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB)
0 1000 65536