记录编号	14876	评测结果	AAAAAA
题目名称	[HAOI 2004模拟]数列问题	最终得分	100
用户昵称	EnAsn	是否通过	通过
代码语言	Pascal	运行时间	1.060 s
提交时间	2009-11-06 09:18:12	内存使用	0.12 MiB

program ex;
type
 sz=array[1..100]of boolean;
 ss=array[0..100]of integer;
 zs=array[0..50,0..50]of integer;
var
 ans:ss;
 z,flag:sz;
 f:zs;
 n,avs:longint;
procedure init;
 var
  i,j:integer;
 begin
  assign(input,'dfs3.in');
  assign(output,'dfs3.out');
  reset(input);
  rewrite(output);
  readln(n);
  close(input);
  for i:=1 to n do flag[i]:=true;
  z[1]:=true;z[2]:=true;z[3]:=true;
  z[5]:=true;z[7]:=true;z[11]:=true;
  z[13]:=true;z[17]:=true;z[19]:=true;
  z[23]:=true;z[29]:=true;z[31]:=true;
  z[37]:=true;z[41]:=true;z[43]:=true;
  z[47]:=true;z[53]:=true;z[59]:=true;
  z[61]:=true;z[67]:=true;z[71]:=true;
  z[73]:=true;z[79]:=true;z[83]:=true;
  z[89]:=true;z[97]:=true;
  f[0,0]:=n;
  for i:=1 to n do f[0,i]:=i;
  for i:=1 to n do
   for j:=1 to n do
    if i<>j then
     begin
      if z[i+j] then
       begin
        inc(f[i,0]);
        f[i,f[i,0]]:=j;
       end;
     end;
 end;
procedure print;
 var
  i:integer;
 begin
  inc(avs);
  for i:=1 to n do write(ans[i],' ');
  writeln;
 end;
procedure dfs(step:integer);
 var
  i:integer;
 begin
  for i:=1 to f[ans[step-1],0] do
   if flag[f[ans[step-1],i]] then
     begin
      ans[step]:=f[ans[step-1],i];
      flag[f[ans[step-1],i]]:=false;
      if step=n then print
                else dfs(step+1);
      flag[f[ans[step-1],i]]:=true;
      ans[step]:=0;
     end;
 end;
begin
 init;
 if n=1 then writeln('0') else dfs(1);
 writeln(avs);
 close(output);
end.