Find a multiple
|
Time Limit: 1000MS |
|
Memory Limit: 65536K |
||
|
Total Submissions: 4987 |
|
Accepted: 2158 |
|
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
Source
Ural Collegiate Programming Contest 1999
解题思路：
1、 用抽屉原理，求几个相加的和(s)是所求数（n）的倍数，可以求和(s)对它(n)的余数，余数相同的两个数之差一定能整除（n）。
抽屉原理：
一抽屉原理
原理1： 把多于n个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件。
证明（反证法）：如果每个抽屉至多只能放进一个物体，那么物体的总数至多是n，而不是题设的n+k(k≥1)，故不可能。
原理2 ：把多于mn(m乘以n)个的物体放到n个抽屉里，则至少有一个抽屉里有不少于m+1的物体。
证明（反证法）：若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符，故不可能。
原理3 ：把无穷多件物体放入n个抽屉，则至少有一个抽屉里 有无穷个物体。
原理1 、2 、3都是第一抽屉原理的表述。
第二抽屉原理
把（mn－1）个物体放入n个抽屉中，其中必有一个抽屉中至多有（m—1）个物体(例如，将3×5-1=14个物体放入5个抽屉中，则必定有一个抽屉中的物体数少于等于3-1=2)。
证明（反证法）：若每个抽屉都有不少于m个物体，则总共至少有mn个物体，与题设矛盾，故不可能。
1. 任意5个自然数中，必可找出3个数，使这三个数的和能被3整除。
分析：解这个问题，注意到一个数被3除的余数只有0，1，2三个，可以用余数来构造抽屉。
解：以一个数被3除的余数0、1、2构造抽屉，共有3个抽屉。任意五个数放入这三个抽屉中，若每个抽屉内均有数，则各抽屉取一个数，这三个数的和是3的倍数，结论成立；若至少有一个抽屉内没有数，那么5个数中必有三个数在同一抽屉内，这三个数的和是3的倍数，结论亦成立
程序代码：
。
#include<stdio.h>
#include<string.h>
#define N 10005
int a[N],b[N]; //数组 a 存放原始数据。 数组b 当做抽屉存放余数。
int main()
{
int n,m,i,j,k,t,f,s;
while(scanf("%d",&n)!=EOF)
{
memset(b,0,sizeof(b));
// memset(c,0,sizeof(c));
for(i=0;i<n;i++)
{
scanf("%d",&a[i]); //抽屉原理：余数做抽屉，和做苹果。
}
s=0;
k=0;
t=0;
f=0;
for(i=0;i<n;i++)
{
s=s+a[i]; //依次求和，
if(s%n==0) // 并且求一次判定依次
{
f=1;
t=i+1;
k=0;
break; //得到想要的结果就要立即跳出。
}
else if(b[s%n]==0)
{
b[s%n]=i+1;
f=0; // f 变量来控制是否有结果需要输出。
}
else if(b[s%n]!=0) // 第二次余数相同的和。
{
f=1;
t=i+1; //注意赋值的大小，所需数据的位数
k=b[s%n];
break;
}
else
f=0;
}
if(f==1)
{
printf("%d ",t-k);
for(i=k;i<t;i++)
printf("%d ",a[i]);
}
else
printf("0 ");
}
}