Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

鸽巢原理 16Ms AC

Posted by su03121231 at 2013-08-03 15:26:25 on Problem 2356
//http://www.cnblogs.com/ACShiryu/archive/2011/08/09/poj2356.html
//这个blog对此原理讲的比较好

#include<stdio.h>
int a[10010],sum[10010];
int main()
{
	int n,i,j,flag;
	while(scanf("%d",&n)!=EOF)
	{
		flag=0;
		for(i=1;i<=n;i++)
			scanf("%d",&a[i]);
		sum[0]=0;
		for(i=1;i<=n;i++)
		{
			sum[i]=(sum[i-1]+a[i])%n;
			if(sum[i]==0)
			{
				printf("%d\n",i);
				for(j=1;j<=i;j++)
					printf("%d\n",a[j]);
				flag=1;
				break;
			}
		}
		if(flag==0)
		{
			for(i=1;i<=n;i++)
			{
				for(j=i+1;j<=n;j++)
				{
					if(sum[i]==sum[j])
					{
						printf("%d\n",j-i);
						for(++i;i<=j;i++)
						{
							printf("%d\n",a[i]);
						}
						flag=1;
						goto over;
					}
				}
			}
		}
over:
		if(!flag)
			printf("0\n");
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator