记录编号	366725	评测结果	AAAAAAAAAA
题目名称	[USACO 1.5.4] 跳棋的挑战	最终得分	100
用户昵称	Mealy	是否通过	通过
代码语言	C++	运行时间	1.873 s
提交时间	2017-01-25 18:07:40	内存使用	0.31 MiB

//64
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>


using namespace std;

int n;
int cutline;
int ans=0;

int num=0;

int save[105];

void PreDo()
{
	scanf("%d",&n);
	cutline=(1<<n)-1;
//	printf("%d ",cutline);
}

void DFS(int unablerow,int unableslash,int unablebackslash,int floor)
{
//	printf("%d ",floor);
//	printf("%d ",unablerow);
	if(unablerow==cutline)
	{
		ans++;
		if(ans<=3)
		{
			for(int i=1;i<=n;i++)
			{
				printf("%d ",save[i]);
			}
			printf("\n");
		}
	}
	else
	{
		int ablepos=~(unablerow|unableslash|unablebackslash);
//		printf("%d ",ablepos);
		int becut=(ablepos&cutline);
//		printf("%d ",becut);
		while(becut)
		{
			int putpos=becut&(-becut);
//			printf("%d ",putpos);
			int tmpputpos=putpos;
			int tmppos=0;
			while(tmpputpos)
			{
				tmpputpos/=2;
				tmppos++;
			}
//			printf("%d ",tmppos);
			save[floor]=tmppos;
			becut-=putpos;
			DFS(unablerow+putpos,(unableslash+putpos)<<1,(unablebackslash+putpos)>>1,floor+1);
		}
	}
}

void Out()
{
	printf("%d\n",ans);
}

int main()
{
	freopen("checker.in","r",stdin);
	freopen("checker.out","w",stdout);
	PreDo();
	DFS(0,0,0,1);
	Out();
	return 0;
}