比赛 |
20121106 |
评测结果 |
AAAAAAAA |
题目名称 |
过河 |
最终得分 |
100 |
用户昵称 |
不列颠呆毛 |
运行时间 |
0.059 s |
代码语言 |
C++ |
内存使用 |
3.29 MiB |
提交时间 |
2012-11-06 10:20:18 |
显示代码纯文本
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
int n,a[1010],b[1010],p[1010];
int now=0,t=0;
queue<int> que[2];
int check(int x){
int tt=t;
if (x==0 || x==n+1) return 1;
tt%=a[x]+b[x];
if (tt>=1 && tt<=a[x]) return 1;
return 0;
}
int main(){
freopen("rivera.in","r",stdin);
freopen("rivera.out","w",stdout);
scanf("%d",&n);
for (int i=1; i<=n; i++)
scanf("%d%d",&a[i],&b[i]);
que[0].push(0);
while (++t<=2000 && que[now].size()){
memset(p,0,sizeof(p));
while (que[now].size()){
int x=que[now].front();
que[now].pop();
for (int i=max(0,x-5); i<=min(n+1,x+5); i++)
if (!p[i] && check(i)) { p[i]=1; que[!now].push(i); }
if (p[n+1]) {cout<<t; return 0;}
}
now=!now;
}
cout<<"NO";
return 0;
}