Description
“汉诺塔”,是一个众所周知的古老游戏。现在我们把问题稍微改变一下:如果一共有4根柱子,而不是3根,那么至少需要移动盘子多少次,才能把所有的盘子从第1根柱子移动到第4根柱子上呢?
为了编程方便,您只需要输出这个结果mod 10000的值。
Input
该题含有多组测试数据,每组一个正整数n。(0<n<=50000)
Output
一个正整数,表示把n个盘子从第1根柱子移动到第4根柱子需要的最少移动次数mod 10000的值。
Sample Input
15
Sample Output
129
Solution
找规律,移动次数是递增的,规律为+2 +2 +4 +4 +4 +8 +8 +8 +8 ...是等差(组)和等比(值)数列的结合,下一组就是5个16了。#include <set> #include <map> #include <list> #include <cmath> #include <stack> #include <queue> #include <ctime> #include <string> #include <cstdio> #include <vector> #include <cctype> #include <climits> #include <sstream> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <functional> #define strend string::npos #define ms(a) memset(a,0,sizeof(a)) #define rep(a,v,b) for(int a=v;a<b;a++) #define repe(a,v,b) for(int a=v;a<=b;a++) typedef long long LL; const LL LINF = LLONG_MAX / 2; const int INF = INT_MAX / 2; const int MAXN = 300000+ 10; const int MOD = 1000000009; int gcd(int a, int b) { if (!b)return a; return gcd(b, a%b); } /*(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/ /*(◕‿‿◕) 签订契约,成为马猴烧酒吧! (◕‿‿◕)*/ /*(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/ using namespace std; LL a[50010]={1}; void init() { LL bound=2,num=2; int i=1; while(i<50000) { for(int j=0;j<bound;j++) { a[i]=a[i-1]+num; a[i]%=10000; i++; } bound++; num*=2; num%=10000; } } int main() { init(); int n; while(cin>>n) { n--; printf("%I64d\n",a[n]);// } return 0; }
欢迎转载,请保留出处与链接。Ocrosoft » FZU 1036 四塔问题