2356 Find a multiple 抽屜原理 給定n個數，求其中的任意一個子集滿足集合中的每個元素值加和正好是n的倍數

Find a multiple

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 2547	Accepted: 1109	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很大，直接搜尋顯然是不行的。後來在組合數學書上找到了這個例題（暈，之前白看了，居然把這個經典的題目都給忘了），是抽屜原理的典型應用。
　　假定n個數為a1，a2，...，an，前n項和分别是S1、S2、...、Sn，那麼如果有一個Si模n是0，就是答案，否則，n個數模n的餘數隻能在1到n - 1之間，把餘數作為抽屜，顯然n個數放到n - 1個抽屜裡面，肯定有兩個數餘數相等，這樣取它們的差就得到了結果，算法複雜度是O(n)的。
      

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[11001],vis[11001],s[11001];
int main()
{
    int n;
    while(scanf("%d",&n)==1)
    {
        int pos,len=0;
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            s[i]=(s[i-1]+a[i])%n;
            if(len) continue;//已經找到解
            int mod=s[i];
            if(mod==0)
            {
                pos=1,len=i;
                continue;
            }
            if(vis[mod]==0)
            {
                vis[mod]=i;
            }
            else
            {
                len=i-vis[mod];
                pos=vis[mod]+1;
            }
        }
        printf("%d/n",len);
        for(int i=pos;i<pos+len;i++) printf("%d/n",a[i]);
    }
    return 0;
}