poj 2356 暴力或者組合數學

poj 2356 暴力或者組合數學

Find a multiple Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 6281 Accepted: 2740 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個數問你存不存在k個數(1<=k<=n)使得其和能整出n；能的話輸出其個數及數，不能的話輸出0（沒有不可能的情況，詳情請往下看）

先貼一個暴力的代碼；

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define N 100010
#define LL long long
#define mem(a) memset(a,0,sizeof(a));
#define mem_1(a) memset(a,-1,sizeof(a));
using namespace std;
LL a[N];
int n;
int i,j;
int work()
{
    for(i=0; i>n)
    {
        for(int b=0; b> a[b];
        work();
        cout<之前是因為看鴿笼原理（抽屜原理）才找到的這道題  木想到這麼水。。。
現在介紹下鴿笼原理：
    簡單定義： “如果有五個鴿子笼，養鴿人養了6只鴿子，那麼當鴿子飛回笼中後，至少有一個笼子中裝有2只鴿子。”這個簡單的事實就是著名的鴿笼原理，在我們國家更多地稱為抽屜原理。
  對於這道題，我們先設sum[1]=a[1],sum[2]=a[1]+a[2],sum[3]=a[1]+a[2]+a[3],sum[n]=a[1]+a[2]+....a[n];
如果存在sum[i]正好是n的倍數，直接輸出就是，但若沒有存在，則sum[i]%n必定屬於[1,n-1],因為sum[i]有n項，那麼鴿笼原理來了，由鴿笼原理知必定有一對sum[i]==sum[j]&&i!=j,而這兩個sum的差也就是n的倍數；所以只需要輸出i+1到j的值即可，也解釋了為啥沒有不可能的情況。
下面貼上代碼；
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define N 100010
#define LL long long
#define mem(a) memset(a,0,sizeof(a));
#define mem_1(a) memset(a,-1,sizeof(a));
using namespace std;
int n;
int f[N];
int sum[N];
int pos[N];
void work()
{
    memset(pos, -1, sizeof(pos));
    pos[0] = 0;
    for (int i = 1; i <= n; i++)
        if (pos[sum[i]] == -1)
            pos[sum[i]] = i;
        else
        {
            printf("%d\n", i - pos[sum[i]]);
            for (int j = pos[sum[i]] + 1; j <= i; j++)
                printf("%d\n", f[j]);
            return;
        }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &f[i]);
    sum[0] = f[0] = 0;
    for (int i = 1; i <= n; i++)
        sum[i] = (sum[i - 1] + f[i]) % n;
    work();
    return 0;
}