比赛 |
20121106 |
评测结果 |
WEEEEEEE |
题目名称 |
过河 |
最终得分 |
0 |
用户昵称 |
CAX_CPG |
运行时间 |
0.843 s |
代码语言 |
Pascal |
内存使用 |
38.54 MiB |
提交时间 |
2012-11-06 11:33:33 |
显示代码纯文本
uses math;
var f:array[-1..1000,-1..10000]of longint;
a,b:array[0..1001]of longint;
i,n:longint;
function g(x,y,z:longint):longint;
var i:longint;
begin
if f[x,y]<>f[-1,-1] then exit(f[x,y]);
if x=n+1 then begin f[x,y]:=0;exit(0);end;
if x>=n-4 then begin f[x,y]:=1;exit(1);end;
for i:=1 to 5 do
begin
if (x+i<=n+1) then if (y mod(a[x+i]+b[x+i])+1<=a[x+i])or(x+i=n+1)
then if x+i<>z then f[x,y]:=min(f[x,y],g(x+i,y+1,x)+1);
if (x-i>=0)then if (y mod(a[x-i]+b[x-i])+1<=a[x-i])or(x-i=0)
then if x-i<>z then f[x,y]:=min(f[x,y],g(x-i,y+1,x)+1);
end;
if x<>z then f[x,y]:=min(f[x,y],g(x,y+1,x)+1);
exit(f[x,y]);
end;
begin
assign(input,'rivera.in');reset(input);
assign(output,'rivera.out');rewrite(output);
readln(n);
for i:=1 to n do readln(a[i],b[i]);
a[n+1]:=1;b[n+1]:=1;a[0]:=1;b[0]:=1;
fillchar(f,sizeof(f),$7f);
if g(0,0,-1)<>f[-1,-1]then writeln(g(0,0,-1))else writeln('NO');
end.