来源:http://poj.org/problem?id=2356
题意:有n个数,求是否存在一些数的和是n的倍数。若存在,输出即可。不存在,输出0.
思路:鸽巢原理的题目,组合数学课本上的原题。可以把和求出来,然后对n取余,因为有n个和,对n取余,如果余数中没有出现0,根据鸽巢原理,一定有两个数的余数相同,两个和想减就是n的倍数。如果余数出现0,自然就是n的倍数。也就是说,n个数中一定存在一些数的和是n的倍数。求余输出即可。
代码:
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
#define CLR(arr,val) memset(arr,val,sizeof(arr))
const int N = 10010;
int num[N],sum[N],pos[N];
bool flag[N];
int main(){
//freopen("1.txt","r",stdin);
int n;
while(scanf("%d",&n) != EOF){
CLR(num,0);
CLR(sum,0);
CLR(pos,-1);
CLR(flag,false);
for(int i = 1; i <= n; ++i){
scanf("%d",&num[i]);
sum[i] = sum[i-1] + num[i];
}
for(int i = 1;i <= n; ++i){
int x = sum[i] % n;
if(flag[x]){
int y = pos[x];
printf("%d\n",i - y);
for(int j = y+1; j <= i; ++j)
printf("%d\n",num[j]);
break;
}
if(x == 0){
printf("%d\n",i);
for(int j = 1; j <= i;++j)
printf("%d\n",num[j]);
break;
}
flag[x] = true;
pos[x] = i;
}
}
return 0;
}
分享到:
相关推荐
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ1584-A Round Peg in a Ground Hole 解题报告+AC代码
北大POJ2488-A Knight's Journey 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ1584 -A Round Peg in a Ground Hole 测试数据。数据来源 Mid-Atlantic 2003 问题D
北大POJ2031-Building a Space Station【Prim+计算几何】 POJ2031-Building a Space Station【Prim+计算几何】
北大POJ1942-Paths on a Grid 解题报告+AC代码
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1005-I Think I Need a Houseboat 解题报告+AC代码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1048,加强版的约瑟夫问题 难度中等