[USACO Mar]石子游戏

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file rocksa.in Output file rocksa.out

【题目描述】


在奶牛们回家休息之前,Farmer_Jnhn想让它们做一个智力游戏。

游戏的棋盘由地面上N (1≤N≤15个)相同的洞洞构成,初始状态均为空。游戏的玩法是:走一步要么是把一颗石子填在一个原来是空的洞洞里,要么是从原来不空的洞洞里取走石子。游戏的状态定义成哪些洞洞填了石子,哪些洞洞没有填石子。游戏的目标是达到所有可能的状态一次且仅一次,然后回到所有洞洞全为空的初始状态。

奶牛们玩这个游戏可费了脑筋了下面是一个例子:

洞洞

步数1 2 3

0 O O O 初始状念

1 O O X 放一棵石子在第3洞

2 X O X 放一颗石子在第1洞

3 X O O 取走第3洞的石子

4 X X O 放一颗行子住笫2洞

5 O X O 取走第1洞的石子

6 O X X 放一颗石子在第3洞

7 X X X 放一颗石子在第1洞

         现在,奶牛纠结了!它们必须从某个洞洞取走一颗石子,但无论取走哪颗石子,都要回到一个曾经到达过的状念。例如,如果取走笫2个洞洞的石子,到达状态(X O X),这个状态在第2步已经出现过。

         以下是一个N=3的合法移动方案:

         洞洞

步数1 2 3

0 O O O 初始状态

1 O X O 放一颗石子在第2洞

2 O X X 放一颗石子在第3洞

3 O O X 取走第2洞的石子

4 X O X 放一颗石子在第1洞

5 X X X 放一颗石子在第2洞

6 X X O 取走第3洞的石子

7 X O O 取走第2洞的石子

8 O O O 取走第1洞的石子

             奶牛们玩得精疲力竭,想得到你的帮助。请你写一个程序,给定N,求出一个合法的移动顺序,来赢得游戏。如果有多个方案,任求一个即可。


【输入格式】

第1行:一个整数N

【输出格式】


第1--2^N+1行:每行一个长度为N的字符串,串中仅包含'O'和'X'(O代表空洞洞,X表示不空的洞洞)。串中第j个字符表示第j个洞洞的状态。第1行和最后一行都是全'O'的状态。


【样例输入】

3

【样例输出】

OOO
OXO
OXX
OOX
XOX
XXX
XXO
XOO
OOO

【提示】

在此键入。

【来源】

在此键入。