题目描述

G最后在规定时间内完成了任务，Alice只能放行。
出了房间，G的左边是一条继续前进的道路，右边是一个池塘。池塘中有序的排列着一排数量相同石块和荷叶。
正在G准备向左走继续前进的时候，D和Z爬完了楼梯，出现在了池塘的另一边。D和Z可以踩着石块通过池塘，并且每步可以跨两个单位长度（假定相邻两个物体之间的距离为一个单位长度）。
当前池塘中荷叶与石块的排列如下：（字母X为荷叶，O为石块）
XXXXXOOOOO
显而易见，D和Z是无法通过池塘的。正在她们一筹莫展的时候，G在岸边发现了一个机关。机关中的黑色白色石子分别代表石块和荷叶，移动石子便能够移动相应的石块与荷叶。移动规则如下：
石子靠右排列，左侧有两个空位，每次操作可以将相邻的任意两个石子移动到空位上，但左右位置不可交换。
由于G刚才搬完皇后石像，身心疲惫，她希望你帮她找到移动石子的步骤，使得D和Z可以踩着石头通过池塘。当然，时间紧迫，步骤越少越好。

输入

一个整数n（4≤n≤30），表示石块和荷叶的数量。

输出

输出移动步骤。
其中第一行为初始状态，从左到右一次为n个荷叶，n个石块，2个空位。
最后一行为末状态，规定末状态是2个空位在最左侧。
大写字母X表示荷叶，大写字母O表示石块，下划线_表示空位。

思路

当n=4时我们可以很容易的找出解决方法，而当n>4时可以两步把它变成n-1，一直进行上面的操作就可以了

const
  maxn=1000;
var
  b:array[1..maxn]of char;
  pt,i,n,num:integer;
procedure print;
var
  i:integer;
begin
  inc(num);
  for i:=1 to 2*(n+1) do write(b[i]);
  writeln;
end;
procedure move(k:integer);
var
  i:integer;
begin
  for i:=0 to 1 do
    begin
      b[pt+i]:=b[k+i];
      b[k+i]:='_';
    end;
  pt:=k;
  print;
end;
procedure mv(n:integer);
begin
  if n=4 then
    begin
      move(4);
      move(8);
      move(2);
      move(7);
      move(1);
    end
  else
    begin
      move(n);
      move(2*n-1);
      mv(n-1);
    end;
end;
begin
  assign(input,'pond.in'); reset(input);
  assign(output,'pond.out'); rewrite(output);
  readln(n);
  for i:=1 to n do b[i]:='X';
  for i:=n+1 to 2*n do b[i]:='O';
  b[i+1]:='_';
  b[i+2]:='_';
  pt:=2*n+1;
  num:=-1;
  print;
  mv(n);
end.