{$q-,r-,s-}
const
  maxn=1002;
var
  n,m,max,ms,mi:integer;
  a,b,bel,ind:array[1..maxn]of integer;
  G:array[1..maxn,0..maxn]of integer;
  mk,f,st:array[0..maxn,0..maxn]of integer;
  ls:array[1..maxn,0..3]of integer;
  sel:array[1..maxn]of boolean;
procedure swap(var a,b:integer);
  var
    c:integer;
  begin
    c:=a;a:=b;b:=c;
  end;
procedure sort(p,q:integer);
  var
    i,j,mid:integer;
  begin
    i:=p;j:=q;
    mid:=ind[p+random(q-p+1)];
    repeat
      while ls[ind[i]][0]<ls[mid][0] do inc(i);
      while ls[ind[j]][0]>ls[mid][0] do dec(j);
      if i<=j then
      begin
        if i<j then swap(ind[i],ind[j]);
        inc(i);
        dec(j);
      end;
    until i>j;
    if i<q then sort(i,q);
    if j>p then sort(p,j);
  end;
procedure readdata;
  var
    i:integer;
  begin
    fillchar(mk,sizeof(mk),0);
    m:=0;
    read(n);
    for i:=1 to n do
    begin
      read(a[i],b[i]);
      if mk[a[i],b[i]]>0 then
        begin
          bel[i]:=mk[a[i],b[i]];
          inc(ls[mk[a[i],b[i]]][3]);
        end else
        begin
          inc(m);
          bel[i]:=m;
          ls[m][0]:=a[i];
          ls[m][1]:=b[i];
          ls[m][2]:=n-a[i]-b[i];
          ls[m][3]:=1;
          mk[a[i],b[i]]:=m;
          ind[m]:=m;
        end;
    end;
    sort(1,m);
  end;
procedure print;
  var
    s,i,j:integer;
  begin
    s:=ms;
    i:=mi;
    fillchar(sel,sizeof(sel),0);
    while i>0 do
    begin
      sel[i]:=true;
      j:=i;
      i:=st[s,i];
      dec(s,ls[j][2]);
    end;
    write(n-max);
    for i:=1 to n do
    if not sel[bel[i]] then
      write(' ',i);
    writeln;
  end;
procedure main;
  var
    s,i,j,x,y:integer;
  begin
    for x:=1 to m do
    begin
      i:=ind[x];
      G[i,0]:=0;
      if ls[i][2]<=0 then continue;
      for y:=succ(x) to m do
      begin
        j:=ind[y];
        if ls[j][2]<=0 then continue;
        if (ls[i][0]+ls[i][2]<=ls[j][0])and(ls[i][1]>=ls[j][1]+ls[j][2])and(ls[i][2]+ls[j][2]<=n) then
        begin
          inc(G[i,0]);
          G[i,G[i,0]]:=j;
        end;
      end;
    end;
    fillchar(f,sizeof(f),$FF);
    for x:=1 to m do
    begin
      i:=ind[x];
      if ls[i][2]>0 then
      begin
        f[ls[i][2],i]:=ls[i][3];
        st[ls[i][2],i]:=0;
      end;
    end;
    for s:=1 to n-1 do
      for x:=1 to m do
      begin
        i:=ind[x];
        if (f[s][i]>-1) then
        begin
          for y:=1 to G[i,0] do
          begin
            j:=G[i,y];
            if (s+ls[j][2]<=n)and(f[s,i]+ls[j][3]>f[s+ls[j][2],j]) then
            begin
              f[s+ls[j][2],j]:=f[s,i]+ls[j][3];
              st[s+ls[j][2],j]:=i;
            end;
          end;
        end;
      end;
    ms:=0;
    mi:=0;
    max:=0;
    for s:=1 to n do
      for i:=1 to m do
      if f[s][i]>max then
      begin
        max:=f[s][i];
        ms:=s;
        mi:=i;
      end;
    print;
  end;
begin
  while not seekeof do
  begin
    readdata;
    main;
  end;
end.

• ACed. (0) Jet407 2005-05-08 13:13:29
  • Re:ACed. (19) ACM05002 2005-08-09 13:03:29
    • RE (23) Sempr 2006-03-19 18:38:22