比赛 |
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.