游客 Signup | Login
中文 | En

1042 - 贴瓷砖

通过次数

0

提交次数

0

Time Limit : 1 秒 Memory Limit : 32 MB

有一块大小是 2 n 的墙面，现在需要用2种规格的瓷砖铺满，瓷砖规格分别是 2 1 和 2 * 2，请计算一共有多少种铺设的方法。

Input

输入的第一行包含一个正整数T（T<=20），表示一共有T组数据，接着是T行数据，每行包含一个正整数N（N<=30），表示墙面的大小是2行N列。

Output

输出一共有多少种铺设的方法，每组数据的输出占一行。

Examples

Input Format

3
2
8
12

Output Format

3
171
2731

Solution C

#include<stdio.h>

int main()
{
	int t,n,i;
	double a[30];
	a[0]=1;
	a[1]=3;
	for(i=2;i<30;i++)
		a[i]=a[i-1]+2*a[i-2];
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		printf("%.lf\n",a[n-1]);
	}
	return 0;
}

Solution C++

#include<stdio.h>

int main()
{
	int t,n,i;
	double a[30];
	a[0]=1;
	a[1]=3;
	for(i=2;i<30;i++)
		a[i]=a[i-1]+2*a[i-2];
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		printf("%.lf\n",a[n-1]);
	}
	return 0;
}

Solution Java

import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		 int a=sc.nextInt();
		 int[] b=new int[31];
		 b[1]=1;
		 b[2]=3;
		 for(int i=3;i<31;i++){
			  b[i]=b[i-1]+2*b[i-2];  
		  }
		while(a--!=0){
		  System.out.println(b[sc.nextInt()]);
		}
	}
}

Solution Python

# coding=utf-8
def cg(x,y):
    r=1
    for c in range(x):
        r=r*(y-c)/(c+1)
    return int(r)
a=int(input())
for i in range(a):
    count=0
    b=int(input())
    for j in range(int(b/2+1)):
        count=count+cg(j,b-j)*(2**j)
    print(count)
请先登陆