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