比赛 20120707 评测结果 WWWWWWWWWWWWWWWWWTWW
题目名称 修整数列 最终得分 0
用户昵称 fuhao 运行时间 2.308 s
代码语言 Pascal 内存使用 2.45 MiB
提交时间 2012-07-07 11:36:41
显示代码纯文本
const maxn=100001;
var
 xx,yy,c:array[0..maxn] of int64;
 n,i:longint; a,b,t,tt,delt,x,y,start,time,min:int64;
 procedure gcd(a,b:int64;var x,y:int64);
 var tt:int64;
 begin
  if b=0 then
   begin t:=a; x:=1; y:=0; exit; end;
  gcd(b,a mod b,x,y);
  tt:=y; y:=x-a div b*y; x:=tt;
 end;
begin
 assign(input,'seq.in'); reset(input);
 assign(output,'seq.out'); rewrite(output);
 readln(n,a,b);
 if a>b then
  begin tt:=a; a:=b; b:=tt; end;
 gcd(a,b,x,y);
 delt:=b div t;
 x:=x mod delt;
 while x<0 do x:=x+delt;
 for i:=1 to n do
  begin
   read(c[i]);
   if c[i] mod t<>0 then
    begin
     writeln(-1);
     close(input);
     close(output);
     halt;
    end;
   xx[i]:=-c[i] div t*x;
   xx[i]:=xx[i] mod delt;
   while xx[i]-delt>0 do xx[i]:=xx[i]-delt;
   while xx[i]+delt<0 do xx[i]:=xx[i]+delt;
   if xx[i]<0 then xx[i]:=xx[i]+delt;
   yy[i]:=(-c[i]-a*xx[i]) div b; yy[i]:=abs(yy[i]);
  end;
 start:=1;
 repeat
  min:=maxlongint;
  for i:=start to n+1 do
   begin
    if xx[i]=0 then break;
    if min>xx[i] then min:=xx[i];
   end;
  inc(time); t:=i-1;
  for i:=start to t do xx[i]:=xx[i]-min;
  while (start<=n) and (xx[start]=0) do inc(start);
 until start>n;
 start:=1;
 repeat
  min:=maxlongint;
  for i:=start to n+1 do
   begin
    if yy[i]=0 then break;
    if min>yy[i] then min:=yy[i];
   end;
  inc(time); t:=i-1;
  for i:=start to t do yy[i]:=yy[i]-min;
  while (start<=n) and (yy[start]=0) do inc(start);
 until start>n;
 writeln(time);
 close(input); close(output);
end.