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 ?

Input

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

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

3
3 2
4 2
5 2
3
2 0
7 1
3 1

Sample Output

YES
NO

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

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

 

代码:

#include <iostream>
#include<cstdio>
#include<cmath>
#define maxn 10010
typedef long long LL;
using namespace std;
int a[maxn];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        LL sum=0;
        for(int i=0;i<n;i++)
        {
            int p,q;
            scanf("%d%d",&p,&q);
            a[i]=p-q;
            sum+=a[i];
        }
        int ok=1;
        for(int i=0;i<n;i++)
        {
            if(2*a[i]>sum)
            {
                ok=0;
                break;
            }
        }
        if(sum%2==1) ok=0;
        if(ok) printf("YESn");
        else printf("NOn");
    }
    return 0;
}

 

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

Leave a Reply

Your email address will not be published. Required fields are marked *

six − one =

This site uses Akismet to reduce spam. Learn how your comment data is processed.