网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
过河
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | rivera.in | 输出文件 | rivera.out |
【题目描述】
农夫每天去种地都要过一条河,这条河很宽,过河要走上面的木桩。木桩有n支,排成一排,从左岸延伸到右岸,编号从1到n。左岸在1号桩的左边,右岸在n号桩的右边。但这些木桩会定时升降,因此每天他都花不少时间在过河上。所以他想找一种最快过河的方法。
在时刻0,农夫在左岸,他要在最短时间内到达右岸。在任何时刻,每一支桩都只能处于升或降的其中一种状态。升起的桩才可以站上去,农夫只能站在升起的桩上或岸上。
每一支桩在时刻0都是降的状态,接着升起A分钟,降下B分钟,再升起A分钟后,再降下B分钟后,这样一直交替升降下去。例如:A=2,B=3的桩,在时刻0降,在时刻1,2升,在时刻3,4,5降,等等。A和B是常数时间,而且对于每一支桩都可能不同。
设在时刻t农夫站在p桩,那么在时刻t+1,农夫能走到p桩的左右5个桩上或岸上,也可以原地不动,当然桩是可站立的。例如,在5号桩,他能走到1,2,3,4,5,6,7,8,9,10号桩,或到左岸。
请帮农夫找一种能最快到达右岸的方法。
【输入格式】
第一行是桩的数目,n(5<n≤1000)。接下来的n行每一行有两个整数A和B(1≤A,B≤5),用一个空格隔开。按从1到n的顺序描述每一支桩的升和降的间隔时间。
【输出格式】
只有一行,即最早到达右岸的时刻。当不可能到达右岸时,输出“NO”。
【样例输入】
10 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1
【样例输出】
4