NYOJ 45 棋盘覆盖

棋盘覆盖

时间限制： 3000?ms ?|? 内存限制： 65535?KB

难度： 3

描述

在一个2^k×2^k（1<=k<=100）的棋盘中恰有一方格被覆盖，如图1（k=2时），现用一缺角的2×2方格（图2为其中缺右下角的一个），去覆盖2^k×2^k未被覆盖过的方格，求需要类似图2方格总的个数s。如k=1时，s=1;k=2时，s=5

? ? ?

? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

?

?

?

输入

第一行m表示有m组测试数据；
每一组测试数据的第一行有一个整数数k;

输出

输出所需个数s;

样例输入

3123

样例输出

1521

算法分析：

#include<iostream>
#include<string.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		int a[100];
		memset(a,sizeof(a));
		int size;
		cin>>size;
		a[0]=1;
		if(size==1)
			cout<<a[0]<<endl;
		int i,j,k;
		for(i=2;i<=size;++i)
		{
			for(j=0;j<100;++j)
				a[j]=4*a[j];
			a[0]++;
			for(j=0;j<99;++j)
			{
				a[j+1]+=a[j]/10;
				a[j]=a[j]%10;
			}
		}
		
		for(i=99;i>=0;--i)
			if(a[i]) break;
		for(j=i;j>=0;--j)
			cout<<a[j];
		cout<<endl;
	}
	return 0;
}