比赛 20120707 评测结果 C
题目名称 修整数列 最终得分 0
用户昵称 SnowDancer 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2012-07-07 11:58:15
显示代码纯文本
program sqe;
var
  a,b,c,x,y,d,k,n,i,j,l,delta,ans:longint;
  num:array[1..100000] of longint;
  f1,f2:array[0..100001] of longint;
procedure extended_gcd(a,b:longint;var x,y,d:longint);
  begin
    if b=0 then begin
      d:=a;x:=1;y:=0;
    end else begin
      extended_gcd(b,a mod b,x,y,d);
      k:=x;x:=y;y:=k-(a div b)*y;
    end;
  end;
function min(x,y:longint):longint;
  begin  if x<y then exit(x) else exit(y); end;
begin
assign(input,'sqe.in');reset(input);
assign(output,'sqe.out');rewrite(output);
  readln(n,a,b);
  extended_gcd(a,b,x,y,d);
  for i:=1 to n do begin
    read(num[i]);
    if num[i] mod d<>0 then begin
      writeln(-1); close(input); close(output);
      halt;
    end;
    f1[i]:=x*num[i]; f2[i]:=y*num[i];
  end;
  for i:=1 to n do begin
    delta:=abs(f1[i]-f1[i-1])+abs(f2[i]-f2[i-1]);
    while abs((f1[i]+b)-f1[i-1])+abs((f2[i]-a)-f2[i-1])<delta do begin
      inc(f1[i],b); dec(f2[i],b);
    end;
    while abs((f1[i]-b)-f1[i-1])+abs((f2[i]+a)-f2[i-1])<delta do begin
      dec(f1[i],b); inc(f2[i],b);
    end;
  end;
  for i:=n downto 1 do begin
    delta:=abs(f1[i]-f1[i+1])+abs(f2[i]-f2[i+1]);
    while abs((f1[i]+b)-f1[i+1])+abs((f2[i]-a)-f2[i+1])<delta do begin
      inc(f1[i],b); dec(f2[i],b);
    end;
    while abs((f1[i]-b)-f1[i+1])+abs((f2[i]+a)-f2[i+1])<delta do begin
      dec(f1[i],b); inc(f2[i],b);
    end;
  end;
  i:=0;
  while i<=n do begin
    while (f1[i]=0)and(i<n) do inc(i);
    if (i=n) and (f1[i]=0) then break;
    j:=i;  delta:=maxlongint;
    while (f1[j]<>0) and (boolean(f1[j]<0)=boolean(f1[i]<0)) do begin
      delta:=min(f1[j],delta);inc(j);
    end;
    for k:=i to j-1 do dec(f1[k],delta);
    inc(ans);
  end;
  i:=0;
  while i<=n do begin
    while (f2[i]=0)and(i<n) do inc(i);
    if (i=n) and (f2[i]=0) then break;
    j:=i;  delta:=maxlongint;
    while (f2[j]<>0) and (boolean(f1[j]<0)=boolean(f2[i]<0)) do begin
      delta:=min(f2[j],delta);inc(j);
    end;
    for k:=i to j-1 do dec(f2[k],delta);
    inc(ans);
  end;
  writeln(ans);
  close(input); close(output);
end.