HDU 4422 The Little Girl who Picks Mushrooms（模拟）

The Little Girl who Picks Mushrooms

Time Limit: 2000/1000 MS(Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3220 Accepted Submission(s): 1049

Problem Description

It's yet another festival season in Gensokyo. Little girlAlice planned to pick mushrooms in five mountains. She brought five bags withher and used different bags to collect mushrooms from different mountains. Eachbag has a capacity of 2012 grams. Alice has finished picking mushrooms in 0 ≤ n≤ 5 mountains. In the i-th mountain, she picked 0 ≤ w_i ≤ 2012 gramsof mushrooms. Now she is moving forward to the remained mountains. Afterfinishing picking mushrooms in all the five mountains, she want to bring asmuch mushrooms as possible home to cook a delicious soup.
Alice lives in the forest of magic. At the entry of the forest of magic, livethree mischievous fairies, Sunny, Lunar and Star. On Alice's way back home, toenter the forest, she must give them exactly three bags of mushrooms whosetotal weight must be of integral kilograms. If she cannot do so, she must leaveall the five bags and enter the forest with no mushrooms.
Somewhere in the forest of magic near Alice's house, lives a magician, Marisa.Marisa will steal 1 kilogram of mushrooms repeatedly from Alice until she hasno more than 1 kilogram mushrooms in total. So when Alice gets home, what's themaximum possible amount of mushrooms Alice has? Remember that our common sensedoesn't always hold in Gensokyo. People in Gensokyo believe that 1 kilogram isequal to 1024 grams.

Input

There are about 8192 test cases. Proceed to the end offile.
The first line of each test case contains an integer 0 ≤ n ≤ 5, the number ofmountains where Alice has picked mushrooms. The second line contains n integers0 ≤ w_i ≤ 2012, the amount of mushrooms picked in each mountain.

Output

For each test case, output the maximum possible amount ofmushrooms Alice can bring home, modulo 20121014 (this is NOT a prime).

Sample Input

512 512 512 512

100 200 300 400 500

208 308 508 708 1108

Sample Output

1024

792

Hint

In the second sample, if Alicedoesn't pick any mushrooms from the 5-th mountain. She can give (512+512+0)=1024 grams of mushrooms to Sunny, Lunar and

Star. Marisa won't steal anymushrooms from her as she has exactly 1 kilogram of mushrooms in total.

In the third sample, there areno three bags whose total weight is of integral kilograms. So Alice must leaveall the five bags and enter the forest with no mushrooms.

In the last sample:

1.Giving Sunny, Lunar andStar: (208+308+508)=1024

2.Stolen by Marisa: ((708+1108)-1024)=792

Source

2012 Asia ChangChun Regional Contest

Recommend

zhuyuanchen520

2012年长春现场赛D题。可以说是当时的签到题目把。

题目意思：

小女孩去采蘑菇。一共有五座山上有蘑菇，小女孩有五个包，一个包可以装一座山上的蘑菇，每个包的容量都是2012。小女孩采完蘑菇以后回去的路上，路过一个森林，里面住着三位仙女，要求小女孩留下三袋蘑菇，且三袋蘑菇的质量总和为整数倍的KG（这个国家里，1KG=1024g），如果拿不出符合条件的蘑菇，那小女孩就要把五袋蘑菇都留下。

小女孩继续往前走，准备回家，在路上有个巫女，当小女孩的蘑菇数量大于1Kg的时候，就偷走1Kg，直至小女孩的蘑菇重量小于等于1Kg。

问最后小女孩回到家，所能得到的最大蘑菇数

题目输入，给的是小女孩已经采摘了N座山，每座山才Ni g的蘑菇。

解题思路

读了好几遍题目，都没找到题目中20121014这个数字的用处。

我觉得无论如何，最后小女孩到家的蘑菇数总是小于等于1024的，毕竟路上总是有巫女一直在偷蘑菇。

简单分析一下，当N=1，N=2,N=3这几种情况，我们都可以至少拿出一袋已知重量的蘑菇包，在加上两个未知的蘑菇包，凑成1024的整数倍。交给小仙女。

然后剩下的包，我们也总能把重量凑成1024，这样剩下来的重量总是最大的。

所以当N<=3的时候，答案就是1024；

N=4和N=5情况就分别讨论。

N=5是，每个包的质量都是已知的，那我们遍历一下，随机找3个包，看质量和是否为1024的整数倍。是的情况下，在求剩下的两个包的质量最大。

如果没有，5个包都要留下，那答案就是0；

N=4情况，先找三个包凑成1024的整数倍的情况，如果可以，那剩下的一个已知包必然可以和未知包凑成1024 的整数倍，这样最后剩下来的重量最大。

如果不可以，那就选择两个已知包和一个未知包凑1024的整数倍交给小仙女。

这时候就需要求一下剩下的两个已知包质量和最大。

注意处理一下

0 0 0 0 0这类有多个0的情况

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;

int main()
{
	int n;
	int x,y;
	int i,j,k;
	int sum,ans,flag,tag;
	int num[10];
	while(scanf("%d",&n)!=EOF)
	{
		flag=1; tag=0;
		sum=0; ans=0;
		for(i=0;i<n;i++)
			scanf("%d",&num[i]);
		if(n<=3)
			printf("1024\n");
		else
		{
			if(n==5)
			{
				for(i=0;i<n;i++){
					for(j=i+1;j<n;j++){
						for(k=j+1;k<n;k++){
							if((num[i]+num[j]+num[k])%1024==0){
								tag=1; sum=0;
								for(x=0;x<n;x++){
										if(x!=i&&x!=j&&x!=k){
												sum+=num[x];
									}
								}
								if(sum!=0)
									sum=sum%1024?sum%1024:1024;
								else
									sum=0;
								ans=max(ans,sum);
							}
						}
					}
				}
				if(tag)
					printf("%d\n",ans);
				else
					printf("0\n");
			}
			else if(n==4)
			{
				for(i=0;i<n;i++)
				{
					for(j=i+1;j<n;j++)
					{
						for(k=j+1;k<n;k++)
						{
							if((num[i]+num[j]+num[k])%1024==0)
							{
								tag=1;
								ans=1024;
							}
						}
					}
				}
				for(i=0;i<n&&!tag;i++)
				{
					sum=0;
					for(j=i+1;j<n;j++)
					{
						sum=num[i]+num[j];
						if(sum!=0)
							sum=sum%1024?sum%1024:1024;
						else
							sum=0;
						ans=max(ans,sum);
					}
				}
				printf("%d\n",ans);
			}
		}
	}
}