【描述】
“漢諾塔”，是一個眾所周知的古老游戲。現在我們把問題稍微改變一下：如果一共有4根柱子，而不是3根，那么至少需要移動盤子多少次，才能把所有的盤子從第1根柱子移動到第4根柱子上呢？
為了編程方便，您只需要輸出這個結果mod 10000的值。
【輸入】
一個正整數n。（0<n<=50000）
【輸出】
一個正整數，表示把n個盤子從第1根柱子移動到第4根柱子需要的最少移動次數mod 10000的值。
【樣例輸入】
15
【樣例輸出】
129
【分析】
弄出前幾個數，發現規律。
f[1]=1，之后分別是加2個2，加3個4，加4個8，加5個16……
1: #include <stdio.h>
2: #define maxn 50010
3:
4: int a,b;
5: int k=1,t;
6: long long j=1;
7: int n;
8:
9: int main()
10: {
11: freopen("hnoi.in","r",stdin);
12: freopen("hnoi.out","w",stdout);
13:
14: scanf("%d",&n);
15: b=1;
16: for (int i=2;i<=n;++i)
17: {
18: a=b;
19: if (!t)
20: {
21: t=++k;
22: j*=2;
23: j%=10000;
24: }
25: b=(a+j)%10000;
26: --t;
27: }
28: printf("%d\n",b);
29: return 0;
30: }
31: