TopCoder

Thumb mikazuki.munechika.full.1936339
FHVirus
$\fbox{背包問題} 比 \definecolor{p}{RGB}{219,48,122}{\color{p}\fbox{FFT}} 難 QWQ$

User's AC Ratio

92.8% (77/83)

Submission's AC Ratio

64.0% (128/200)

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

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1