浙江财经大学
信工学院ACM集训队

FZU 1036 四塔问题

本文由 Ocrosoft 于 2016-12-02 19:33:09 发表

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 四塔问题

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址