BNU Contest 8-26 G. Gao The Sequence

BNU Contest 8-26 G. Gao The Sequence

BNU Contest 8-26 竞赛题目链接点击这里

G. Gao The Sequence

Time Limit: 2000ms
Memory Limit: 65536KB

64-bit integer IO format: %lld      Java class name: Main

You are given a sequence of integers, A1,A2,…,An. And you are allowed a manipulation on the sequence to transform the origin sequence into another sequence B1,B2,…,Bn(Maybe the two sequences are same ). The manipulation is specified as the following three steps:

1.Select an integer Ai and choose an arbitrary positive integer delta as you like.

2.Select some integers Aj satisfying j < i, let’s suppose the selected integers are Ak1,Ak2,…,Akt , then subtract an arbitrary positive integer Di from Aki (1 ≤ i ≤ t) as long as sum(Di) = delta.

3.Subtract delta from Ai.

The manipulation can be performed any times. Can you find a way to transform A1,A2,…,An to B1,B2,…,Bn ?


The input consist of multiple cases. Cases are about 100 or so. For each case, the first line contains an integer N(1 ≤ N ≤ 10000) indicating the number of the sequence. Then followed by N lines, ith line contains two integers Ai and Bi (0 ≤ Bi ≤ Ai ≤ 4294967296).


Output a single line per case. Print “YES” if there is a certain way to transform Sequence A into Sequence B. Print “NO” if not.

Sample Input

Sample Output

这个题也就是看起来有些吓人而已 = =  实际上水的不行

既然我可以任选delta那就表明我可以选择delta为2  每次都把两个数各减掉一,如果能够减到零,即差值的和是偶数的话 那么就可以了 ,如果做不到 ,那么别的方法也做不到 ,因为每次减二已经是必定可行的策略了 ,可以保证在数据符合题意的情况下,最后sumdelta(差值的和)=0  然后加两个特判,一个就是如果sumdelta为奇数,一定不行,另一个就是 如果有一个差值大于了sumdelta/2那么他不可能减到零  ,,然后就没有什么需要注意的了




2 thoughts on “BNU Contest 8-26 G. Gao The Sequence


电子邮件地址不会被公开。 必填项已用*标注

2 × 2 =