> //官方测试数据:http://www.informatik.uni-ulm.de/acm/Regionals/1998/
type
 stack=array[1..7]of longint;
const
 com:array[1..5]of string[3]=('ADD','DIV','DUP','MUL','SUB');
var
 a,b,f:array[0..10]of longint;
 s:stack;
 test,n,m,i,p,ID:longint;

function cal(x,y,z:longint):longint;
 begin
  case z of
   1:cal:=x+y;
   2:cal:=y div x;
   4:cal:=x*y;
   5:cal:=y-x;
  end;
 end;

function command(var s:stack; var p:longint; i:longint):boolean;
 var
  next:longint;
 begin
  if i<>3 then
   begin
    next:=cal(s[p],s[p-1],i);
    if abs(next)>30000 then exit(false);
    dec(p); s[p]:=next;
   end
  else begin inc(p); s[p]:=s[p-1]; end;
  exit(true);
 end;

function judge:boolean;
 var
  i,j,p:longint;
  s:stack;
 begin
  for i:=1 to n do
   begin
    fillchar(s,sizeof(s),0);
    p:=1; s[1]:=a[i];
    for j:=1 to f[0] do
     begin
      if (f[j]=2)and(s[p]=0) then exit(false);
      if not command(s,p,f[j]) then exit(false);
     end;
    if s[p]<>b[i] then exit(false);
   end;
  exit(true);
 end;

function dfs(deep:integer):boolean;
 var
  i,re:longint;
  res:stack;
 begin
  if (p=1)and(s[p]=b[m])and judge then exit(true);
  if (deep=ID)or(p>ID+1-deep) then exit(false);
  for i:=1 to 5 do
   begin
    if ((i<>3)and(p=1))or((i=2)and(s[p]=0)) then continue;
    re:=p; res:=s;
    if not command(s,p,i) then continue;
    inc(f[0]); f[f[0]]:=i;
    if dfs(deep+1) then exit(true);
    dec(f[0]); p:=re; s:=res;
   end;
  exit(false);
 end;

begin
 randomize;
 repeat
  inc(test);
  read(n);
  if n=0 then exit;
  m:=random(n)+1;
  for i:=1 to n do read(a[i]);
  for i:=1 to n do read(b[i]);
  writeln('Program ',test);
  for ID:=0 to 10 do
   begin
    fillchar(f,sizeof(f),0);
    fillchar(s,sizeof(s),0);
    p:=1; s[1]:=a[m];
    if dfs(0) then
     begin
      if f[0]=0 then writeln('Empty sequence')
      else begin
       for i:=1 to f[0]-1 do write(com[f[i]],' ');
       writeln(com[f[f[0]]]);
      end;
      break;
     end;
    if ID=10 then writeln('Impossible');
   end;
  writeln;
 until false;
end.

• Re:再贴个本蒟蒻的pascal的94ms代码~ (38) sjynoip 2011-07-09 14:39:37