鴿巢原理

?

鴿巢原理： n+1個鴿子放入n個窩中，至少有一個窩含有兩只鴿子?

Find a multiple

Time Limit:?1000MS	?	Memory Limit:?65536K
Total Submissions:?5590	?	Accepted:?2434	?	Special Judge

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的倍數

解題思路：

首先，一定存在這樣的集合，它是集合中的一串連續數字，且其和為 N的倍數

證明：

設集合中的數字為 a1,a2,a3,a4,……ai，則設：

S1 = a1

S2 = a1+a2

S3 = a1+a2+a3

Sn = a1+a2+a3+……+an

若 Sn % N = 0,則 Sn 即為所求，

若 Sn % N ！= 0 ，Sn % N 的 范圍 在 【1，N-1】之間 ， 又一共有 N 個余數 ，根據鴿巢原理，一定有兩個余數是相同的，

我們假設為Si 和 Sj，

即有：

Si % N = t

Sj % N = t

那么一定有：

（Si - Sj）% N = 0

所以一定存在符合要求的解，且其集合中的數字是連續的，范圍是【ai，aj】。

證畢。

import java.util.Scanner;public class ACM16 {public static void main(String[] args) {Scanner cin = new Scanner(System.in);int num = cin.nextInt();int[] arr = new int[num], sum = new int[num], b = new int[num];for (int i = 0; i < num; i++) {arr[i] = cin.nextInt();b[i] = -1;}sum[0] = arr[0] % num;b[sum[0]] = 0;int temp = 0, temp1 = 0;for (int i = 1; i < num; i++) {sum[i] = sum[i - 1] + arr[i];sum[i] %= num;if (sum[i] == 0) {temp = -1;temp1 = i;break;}if (b[sum[i]] == -1) {b[sum[i]] = i;} else {temp = b[sum[i]];temp1 = i;break;}}System.out.println(temp1 - temp);for (int i = temp + 1; i <= temp1; i++) {System.out.println(arr[i]);}}
}

?