NYOJ 491ラッキー三角形

import java.util.Scanner;

public class  Main{// 

	static int sum=0,n;

	public static void main(String[] args) {

		Scanner input=new Scanner(System.in);

		while(input.hasNext()){

			n=input.nextInt();

			sum=0;

			char a[]=new char[n];

			sou(a,0);

			System.out.println(sum);

		}

	}

	private static void sou(char[] a, int i) {

		if(i==n){

			char b[]=a;

			int x=0,y=0;

			for(int j=0;j<n;j++){

				if(b[j]=='+')

					x++;

				else

					y++;

			}

			for(int j=n-1;j>0;j--){

				for(int k=0;k<j;k++){

					if(b[k]==b[k+1]){

						b[k]='+';

						x++;

					}

					else{

						b[k]='-';

						y++;

					}

				}

			}

			if(x==y)

				sum++;

			return;

		}

		a[i]='+';

		sou(a,i+1);

		a[i]='-';

		sou(a,i+1);

	}

}







/*

//495114     Accepted  21MS  246 java 2013-07-07 19:02:25 

import java.util.Scanner;

public class Main{// 

	public static void main(String[] args) {

		Scanner input=new Scanner(System.in);

		int a[]=new int[20];

		a[3]=4;a[4]=6;a[7]=12;a[8]=40;a[11]=171;a[12]=410;a[15]=1896;a[16]=5160;a[19]=32757;

		while(input.hasNext()){

			int n=input.nextInt();

			System.out.println(a[n]);

		}

	}

}*/