1097B Petr and a Combination Lock

分手后的思念是犯贱 2022-03-30 09:13 89阅读 0赞

B. Petr and a Combination Lock

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Petr has just bought a new car. He's just arrived at the most known Petersburg's petrol station to refuel it when he suddenly discovered that the petrol tank is secured with a combination lock! The lock has a scale of 360360 degrees and a pointer which initially points at zero:

![58e2000e1b7dc1510062c974ea44c9e3188e72cd.png][]

Petr called his car dealer, who instructed him to rotate the lock's wheel exactly nn times. The ii-th rotation should be aiai degrees, either clockwise or counterclockwise, and after all nnrotations the pointer should again point at zero.

This confused Petr a little bit as he isn't sure which rotations should be done clockwise and which should be done counterclockwise. As there are many possible ways of rotating the lock, help him and find out whether there exists at least one, such that after all nn rotations the pointer will point at zero again.

Input

The first line contains one integer nn (1≤n≤151≤n≤15) — the number of rotations.

Each of the following nn lines contains one integer aiai (1≤ai≤1801≤ai≤180) — the angle of the ii-th rotation in degrees.

Output

If it is possible to do all the rotations so that the pointer will point at zero after all of them are performed, print a single word "YES". Otherwise, print "NO". Petr will probably buy a new car in this case.

You can print each letter in any case (upper or lower).

Examples

input

Copy

3
    10
    20
    30

output

Copy

YES

input

Copy

3
    10
    10
    10

output

Copy

input

Copy

3
    120
    120
    120

output

Copy

YES

Note

In the first example, we can achieve our goal by applying the first and the second rotation clockwise, and performing the third rotation counterclockwise.

In the second example, it's impossible to perform the rotations in order to make the pointer point at zero in the end.

In the third example, Petr can do all three rotations clockwise. In this case, the whole wheel will be rotated by 360360 degrees clockwise and the pointer will point at zero again.

题意：给了一个圆盘，初始0度，n个角度，可以任意顺时针或者逆时针旋转，经过n次度数，能否回到0度。

题解：最开始我找的是规律，判断度数和是不是360的倍数，或者取模360后的一半是否在其中，就能回到0，结果wa5，别人大多数都是dfs.....两边方向搜，x记录个数，当x==n就判断s是否是360的倍数，就返回真或者否。s记录当前度数和。

c++：

#include<bits/stdc++.h>
    using namespace std;
    int a[20],n;
    bool dfs(int x,int s)
    {
        if(x==n)
            return s%360==0?true:false;
        return dfs(x+1,s+a[x+1])||dfs(x+1,s-a[x+1]);
    }
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        printf(dfs(0,0)?"YES\n":"NO\n");
        return 0;
    }

[58e2000e1b7dc1510062c974ea44c9e3188e72cd.png]: /images/20220330/e00619e42b3d40a5b275183168b45e16.png