比赛 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;
}