记录编号	21011	评测结果	AAAAAAAAAA
题目名称	[NOIP 2007]Hanoi双塔问题	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	Pascal	运行时间	0.030 s
提交时间	2010-11-02 15:28:15	内存使用	0.11 MiB

program hanoi(input,output);

const
  MAXSGNUM=1000000000000000000;

type
  supernum=array[0..12]of int64;

var
  n,i:longint;
  ans:supernum;

procedure m2(var a:supernum);
  var
    i:longint;
    h:int64;
  begin
    h:=0;
    for i:=1 to a[0] do
    begin
      a[i]:=a[i]shl 1+h;

      if a[i]>=MAXSGNUM then
      begin
        dec(a[i],MAXSGNUM);
        h:=1;
      end
      else
        h:=0;
    end;

    if h>0 then
    begin
      inc(a[0]);
      a[a[0]]:=1;
    end;
  end;

procedure print(var a:supernum);
  var
    i:longint;
    fl:int64;
  begin
    write(a[a[0]]);

    for i:=a[0]-1 downto 1 do
    begin
      fl:=MAXSGNUM div 10;

      while fl>0 do
      begin
        write(ans[i] div fl);
        ans[i]:=ans[i] mod fl;
        fl:=fl div 10;
      end;
    end;
    writeln;
  end;

begin
  assign(input,'hanoi.in');
  reset(input);
  assign(output,'hanoi.out');
  rewrite(output);

  readln(n);

  ans[0]:=1;
  ans[1]:=1;
  for i:=1 to n+1 do
    m2(ans);

  dec(ans[1],2);
  print(ans);

  close(input);
  close(output);
end.