lamps.pas

来自「Magio牛的usaco源代码」· PAS 代码 · 共 108 行

{
ID:maigoak1
PROG:lamps
}

program lamps;
const
  maxn=100;
  move:array[0..15]of integer=(0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4);
type
  seq=array[1..maxn]of boolean;
var
  fin,fout:text;
  state:array[0..15]of seq;
  step:array[0..15]of integer;
  on,off:array[1..maxn]of boolean;
  n,c,i,j,tint:integer;
  tseq:seq;
  flag:boolean;
function biggerthan(x,y:seq):boolean;
  var
    i:integer;
  begin
    for i:=1 to n do
      if x[i]>y[i] then begin
        biggerthan:=true;
        exit;
      end
      else if x[i]<y[i] then begin
        biggerthan:=false;
        exit;
      end;
  end;
function convert(s:seq;m:integer):seq;
  var
    i:integer;
  begin
    case m of
      1:for i:=1 to n do convert[i]:=not s[i];
      2:for i:=1 to n do if odd(i) then convert[i]:=not s[i] else convert[i]:=s[i];
      3:for i:=1 to n do if odd(i) then convert[i]:=s[i] else convert[i]:=not s[i];
      4:for i:=1 to n do if i mod 3=1 then convert[i]:=not s[i] else convert[i]:=s[i];
    end;
  end;
procedure judge(s:seq);
  var
    i:integer;
  begin
    for i:=1 to n do begin
      if (on[i]=true) and (s[i]=false) then exit;
      if (off[i]=true) and (s[i]=true) then exit;
    end;
    flag:=true;
    for i:=1 to n do
      write(fout,ord(s[i]));
    writeln(fout);
  end;
begin
  fillchar(on,sizeof(on),0);
  fillchar(off,sizeof(off),0);
  assign(fin,'lamps.in');
  reset(fin);
  readln(fin,n);
  readln(fin,c);
  repeat
    read(fin,i);
    if i=-1 then break;
    on[i]:=true;
  until false;
  repeat
    read(fin,i);
    if i=-1 then break;
    off[i]:=true;
  until false;
  close(fin);

  for i:=0 to 15 do
    step[i]:=move[i];
  fillchar(state,sizeof(state),1);
  state[1]:=convert(state[0],1);
  for i:=2 to 3 do state[i]:=convert(state[i-2],2);
  for i:=4 to 7 do state[i]:=convert(state[i-4],3);
  for i:=8 to 15 do state[i]:=convert(state[i-8],4);

  for i:=0 to 14 do
    for j:=i+1 to 15 do
      if biggerthan(state[i],state[j]) then begin
        tseq:=state[i];state[i]:=state[j];state[j]:=tseq;
        tint:=step[i];step[i]:=step[j];step[j]:=tint;
      end;

  for i:=0 to 15 do begin
    for j:=1 to n do
      write(ord(state[i][j]));
    writeln(' ',step[i]);
  end;

  flag:=false;
  assign(fout,'lamps.out');
  rewrite(fout);
  for i:=0 to 15 do
    if step[i]<=c then
      if not odd(step[i]-c) then
        judge(state[i]);
  if not flag then writeln(fout,'IMPOSSIBLE');
  close(fout);
end.