poj 2356 Find a multiple (鴿巢原理妙用)

 

 

Description

The input contains N natural (i.e. positive integer) numbers ( N <= 10000 ). Each of that numbers is not greater than 15000. This numbers are not necessarily different (so it may happen that two or more of them will be equal). Your task is to choose a few of given numbers ( 1 <= few <= N ) so that the sum of chosen numbers is multiple for N (i.e. N * k = (sum of chosen numbers) for some natural number k).

Input

The first line of the input contains the single number N. Each of next N lines contains one number from the given set.

Output

In case your program decides that the target set of numbers can not be found it should print to the output the single number 0. Otherwise it should print the number of the chosen numbers in the first line followed by the chosen numbers themselves (on a separate line each) in arbitrary order.

If there are more than one set of numbers with required properties you should print to the output only one (preferably your favorite) of them.

Sample Input

5
1
2
3
4
1

Sample Output

2
2
3

【題目大意】

首先輸入一個n，然後給你n個數，讓你從中找到 m個數， 1<=m<=n，使得這m個數的和是n的倍數；如果找不到輸出0；

【分析】

我們先用一個sum數組，將a【0】， a【0】+a【1】，a【0】+a【1】+a【2】......儲存起來；

然後判斷這些數能否整除n，如果能則輸出下標，然後直接從第一個數開始依次輸出即可（題目是special judge，只要找到即可，而且順序也是in arbitrary order.）

然後，關鍵的地方來了，因為sum[I]%n一定是屬於【1~n-1】的，而sum總共有n個，根據鴿巢定理

 

把多於n個的物體放到n個抽屜裡，則至少有一個抽屜裡有2個或2個以上的物體。

所以n個 sum【i】%n中，至少有兩個是一樣的；（因此，此題一定有解，不存在輸出0的情況）

 

如果我們找到，則說明（sum[j]-sum[i]）%n==0 （假設一個是sum【i】，一個是sum【j】，j>i,）

也就是 加在 i j 之間的數的和是 n的倍數，只要依次將他們輸出就可以了。

【代碼如下】

 

#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 10010;
int num[maxn];
int mod[maxn];
int sum[maxn];
int main()
{
	int n;
	cin>>n;
	memset(mod, -1 ,sizeof(mod));
	for(int i=0;i>num[i];
		if(i>0)
			sum[i]=sum[i-1]+num[i];
		else
			sum[i]=num[i];
	}
	int sign=0;
	for(int i=0;i也是參考了，博主的代碼和思路 大神博客 ，代碼中值得注意的技巧是用mod數組來儲存余數。