记录编号	48786	评测结果	AAAAAAAA
题目名称	过河	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.039 s
提交时间	2012-11-06 15:56:53	内存使用	5.72 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
using namespace std;

struct quetype
{
	int pos,tim;
};

int a[1010],b[1010],c[1010];
bool used[1010][2530];//[1000][2520]
queue<quetype> que;

int main(void)
{
	freopen("rivera.in","r",stdin);
	freopen("rivera.out","w",stdout);
	quetype from,to;
	int i,n,maxtim,temp;
	bool get;
	cin>>n;
	for (i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
		c[i]=a[i]+b[i];
	}
	for (maxtim=c[1];maxtim<=2520;maxtim++)
	{
		get=true;
		for (i=1;i<=n;i++)
		{
			if (maxtim%c[i])
			{
				get=false;
				break;
			}
		}
		if (get)
			break;
	}
	to.pos=0;
	to.tim=0;
	used[0][0]=true;
	que.push(to);
	while (!que.empty())
	{
		from=que.front();
		to.tim=from.tim+1;
		for (to.pos=from.pos-5;to.pos<=from.pos+5;to.pos++)
		{
			if (to.pos<0||to.pos>n+1)
				continue;
			if (to.pos!=0&&to.pos!=n+1)
			{
				temp=to.tim%c[to.pos];
				if (!temp)
					temp=c[to.pos];
				if (temp<=a[to.pos])
				{
					temp=to.tim%maxtim;
					if (!used[to.pos][temp])
					{
						used[to.pos][temp]=true;
						que.push(to);
					}
				}
			}
			else
			{
				if (to.pos==n+1)
				{
					cout<<to.tim<<endl;
					return(0);
				}
				else
				{
					temp=to.tim%maxtim;
					if (!used[to.pos][temp])
					{
						used[to.pos][temp]=true;
						que.push(to);
					}
				}
			}
		}
		que.pop();
	}
	cout<<"NO\n";
	return(0);
}