世界末日
时间限制:1000 ms | 内存限制:65535 KB
- 描述
- 世界末日马上就要来临了,当然,每个人都想买到船票,但是由于船票有限,因此需要回答对一个问题才能买票。问题是这样的:给你一个数n (1 <= n <= 10000),之后给n个正整数 (<= 10000),问在这n个数中是否存在一些数的和是n的倍数。
- 输入
- 多组测试数据(最多100组)。首先输入一个数n,然后输入n个数。
- 输出
- 如果能找到一些数的和是n的倍数,输出"YES",否则输出"NO"。
- 样例输入
-
5 5 3 6 7 9
- 样例输出
-
YES
-
第一次看到这个题的时候,果断不会呀。。数学呀数学。。后来只有GG了,当然我喜欢GOOgle。。
-
后来发现网上很多都是只给代码,不给过多的解释。。于是只能靠自己呀。。问题自然而然的转化为:在n个整数的集合A中是否存在A的子集的和是n的倍数。(这里说集合有点不合适。。不满足集合的互异性)。。。答案是肯定的。一定存在。。那怎么证明呢?。。。要真是比赛遇到这样的题只能猜了吧。。就是一定的。。
-
网上有n个不相同的整数的证明。但是这里又有相同的元素。。。
-
#include<iostream> #include<cstdio> #include<cstdlib> #include<vector> #include<algorithm> #include<stack> #include<queue> #include<set> #include<map> #include<string> #include<cstring> using namespace std; const int mx=51000;//这个数据边界的设定让我错了几次。。表示做题经验不足的教训呀。。 char c[mx]; int main() { while(gets(c)){ gets(c); printf("YES\n"); } return 0; }