ac1052.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1052;
const
  maxn=100;
var
  a:array[1..maxn]of longint;
  len:array[1..maxn-1,2..maxn]of byte;
  n,i,j,ans,t:byte;
procedure qsort(s,t:byte);
  var
    p,i,j:byte;
    tmp:longint;
  begin
    if s>=t then exit;
    p:=s+random(t-s+1);
    tmp:=a[p];a[p]:=a[s];
    i:=s;j:=t;
    repeat
      while (i<j) and (a[j]>=tmp) do dec(j);
      if i=j then break;a[i]:=a[j];inc(i);
      while (i<j) and (a[i]<=tmp) do inc(i);
      if i=j then break;a[j]:=a[i];dec(j);
    until i=j;
    a[i]:=tmp;
    qsort(s,i-1);
    qsort(i+1,t);
  end;
function find(r:byte;x:longint):byte;
  var
    l,m:byte;
  begin
    l:=1;
    while l<=r do begin
      m:=(l+r) shr 1;
      if a[m]=x then begin find:=m;exit;end else if a[m]<x then l:=m+1 else r:=m-1;
    end;
    find:=0;
  end;
begin
  repeat
    read(n);
    for i:=1 to n do
      read(a[i]);
    qsort(1,n);

    j:=1;ans:=0;t:=1;
    for i:=2 to n do
      if a[i]=a[j] then
        inc(t)
      else begin
        inc(j);
        a[j]:=a[i];
        if t>ans then ans:=t;
        t:=1;
      end;
    if t>ans then ans:=t;
    n:=j;

    for i:=1 to n-1 do
      for j:=i+1 to n do begin
        t:=find(i-1,a[i]*2-a[j]);
        if t=0 then
          len[i,j]:=2
        else
          len[i,j]:=len[t,i]+1;
        if len[i,j]>ans then ans:=len[i,j];
      end;
    writeln(ans);
  until seekeof;
end.