鴿巢原理

鴿巢原理：

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

Sample Output

題意：

一個集合一共有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】。

證畢。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

<code>import</code>

<code>java.util.Scanner;</code>

<code>public</code>

<code>class</code> <code>ACM16 {</code>

<code>    </code><code>public</code>

<code>static</code> <code>void</code> <code>main(String[] args) {</code>

<code>        </code><code>Scanner cin =</code><code>new</code>

<code>Scanner(System.in);</code>

<code>        </code><code>int</code>

<code>num = cin.nextInt();</code>

<code>        </code><code>int</code><code>[] arr =</code><code>new</code>

<code>int</code><code>[num], sum =</code><code>new</code>

<code>int</code><code>[num], b =</code><code>new</code>

<code>int</code><code>[num];</code>

<code>        </code><code>for</code>

<code>(</code><code>int</code>

<code>i =</code><code>0</code><code>; i &lt; num; i++) {</code>

<code>            </code><code>arr[i] = cin.nextInt();</code>

<code>            </code><code>b[i] = -</code><code>1</code><code>;</code>

<code>        </code><code>}</code>

<code>        </code><code>sum[</code><code>0</code><code>] = arr[</code><code>0</code><code>] % num;</code>

<code>        </code><code>b[sum[</code><code>0</code><code>]] =</code><code>0</code><code>;</code>

<code>temp =</code><code>0</code><code>, temp1 =</code><code>0</code><code>;</code>

<code>i =</code><code>1</code><code>; i &lt; num; i++) {</code>

<code>            </code><code>sum[i] = sum[i -</code><code>1</code><code>] + arr[i];</code>

<code>            </code><code>sum[i] %= num;</code>

<code>            </code><code>if</code>

<code>(sum[i] ==</code><code>0</code><code>) {</code>

<code>                </code><code>temp = -</code><code>1</code><code>;</code>

<code>                </code><code>temp1 = i;</code>

<code>                </code><code>break</code><code>;</code>

<code>            </code><code>}</code>

<code>(b[sum[i]] == -</code><code>1</code><code>) {</code>

<code>                </code><code>b[sum[i]] = i;</code>

<code>            </code><code>}</code><code>else</code>

<code>{</code>

<code>                </code><code>temp = b[sum[i]];</code>

<code>        </code><code>System.out.println(temp1 - temp);</code>

<code>i = temp +</code><code>1</code><code>; i &lt;= temp1; i++) {</code>

<code>            </code><code>System.out.println(arr[i]);</code>

<code>    </code><code>}</code>

<code>}</code>