HDU 4422 The Little Girl who Picks Mushrooms （ 模拟）
2024-02-20 19:06:50
Problem Description
It's yet another festival season in Gensokyo. Little girl Alice planned to pick mushrooms in five mountains. She brought five bags with her and used different bags to collect mushrooms from different mountains. Each bag has a capacity of 2012 grams. Alice has finished picking mushrooms in 0 ≤ n ≤ 5 mountains. In the i-th mountain, she picked 0 ≤ wi ≤ 2012 grams of mushrooms. Now she is moving forward to the remained mountains. After finishing picking mushrooms in all the five mountains, she want to bring as much mushrooms as possible home to cook a delicious soup.
Alice lives in the forest of magic. At the entry of the forest of magic, live three mischievous fairies, Sunny, Lunar and Star. On Alice's way back home, to enter the forest, she must give them exactly three bags of mushrooms whose total weight must be of integral kilograms. If she cannot do so, she must leave all 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 has no more than 1 kilogram mushrooms in total. So when Alice gets home, what's the maximum possible amount of mushrooms Alice has? Remember that our common sense doesn't always hold in Gensokyo. People in Gensokyo believe that 1 kilogram is equal to 1024 grams.
Alice lives in the forest of magic. At the entry of the forest of magic, live three mischievous fairies, Sunny, Lunar and Star. On Alice's way back home, to enter the forest, she must give them exactly three bags of mushrooms whose total weight must be of integral kilograms. If she cannot do so, she must leave all 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 has no more than 1 kilogram mushrooms in total. So when Alice gets home, what's the maximum possible amount of mushrooms Alice has? Remember that our common sense doesn't always hold in Gensokyo. People in Gensokyo believe that 1 kilogram is equal to 1024 grams.
Input
There are about 8192 test cases. Proceed to the end of file.
The first line of each test case contains an integer 0 ≤ n ≤ 5, the number of mountains where Alice has picked mushrooms. The second line contains n integers 0 ≤ wi ≤ 2012, the amount of mushrooms picked in each mountain.
The first line of each test case contains an integer 0 ≤ n ≤ 5, the number of mountains where Alice has picked mushrooms. The second line contains n integers 0 ≤ wi ≤ 2012, the amount of mushrooms picked in each mountain.
Output
For each test case, output the maximum possible amount of mushrooms Alice can bring home, modulo 20121014 (this is NOT a prime).
Sample Input
1
9
4
512 512 512 512
5
100 200 300 400 500
5
208 308 508 708 1108
Sample Output
1024
1024
0
792
Hint
In the second sample, if Alice doesn'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 any mushrooms from her as she has exactly 1 kilogram of mushrooms in total.
In the third sample, there are no three bags whose total weight is of integral kilograms. So Alice must leave all the five bags and enter the forest with no mushrooms.
In the last sample:
1.Giving Sunny, Lunar and Star: (208+308+508)=1024
2.Stolen by Marisa: ((708+1108)-1024)=792
Source
题意难懂，懂了以后就是模拟的水题了。
题意是去五座山采蘑菇，回来以后先给三个精灵共三袋蘑菇，其总数加起来要是1024的倍数。否则答案是0。如果给了精灵，剩下的蘑菇大于1024，则会被不停的偷走1024个，直到<=1024个。
给了n座山的采蘑菇数量，如果n<5，则剩下的山可以采任意的a，0<a<2012。所以n<4时，至少一座山可以去采2012个，其他就选三个去凑1024倍数，所以一定能剩下1024个。
n=4，如果其中三个可以组成1024倍数，则一定可以剩下1024个；如果不能，则要靠剩下那个没有采的山和采过的两座山来凑，所以剩下两座山，两个for来挑出剩下最大的那个组合。
n=5，如果其中三个可以组成1024倍数，则剩下两个不断-1024就是答案，三个for挑选出最大的组合。如果组合不出1024倍数，则答案为0。
然后就是考虑情况的时候要注意细节。不然因此WA很亏。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <cstdlib>
#include<cmath>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <stack>
#include <cctype>
using namespace std;
typedef unsigned long long ull;
#define INF 0xfffffff int main()
{
int k,m,q,p;
int T; int a[],n; while(cin>>T)
{
for(int i=;i<T;++i)
{
cin>>a[i];
}
if(T<)
{
cout<<<<endl;
}else if(T==)
{
int ans=;
m=;
q=;
for(int i=;i<T;++i)
{
for(int j=i+;j<T;++j)
{
for(int k=j+;k<T;++k)
{
if((a[i]+a[j]+a[k])%==)
{
m=;
}
}
}
}
if(m)
{
cout<<<<endl;
continue;
} k=;
for(int i=;i<T;++i)
{
for(int j=i+;j<T;++j)
{
p=a[i]+a[j];
while(p>)
{
p-=;
}
k=max(k,p);
}
}
cout<<k<<endl;
}else if(T==)
{
int ans=;
m=;
for(int i=;i<;++i)
{
for(int j=i+;j<;++j)
{
for(int k=j+;k<;++k)
{
if((a[i]+a[j]+a[k])%==)
{
m=;
q=;
for(p=;p<;++p)
{
if(p!=i&&p!=j&&p!=k)
{
q+=a[p];
}
} while(q>)
{
q-=;
}
ans=max(ans,q);
} } }
}
if(m)
{
cout<<ans<<endl;
}else
{
cout<<<<endl;
}
} }
return ;
}
最新文章
- 数据结构快速回顾——平衡二叉树 AVL （转）
- Java入门记(四)：容器关系的梳理（上）——Collection
- python极客学院爬虫V1
- Navicat for MySQL连接MYSQL出错,错误代码1045的解决方法
- Java实验四和实验五
- c#写windows服务（转）
- js 除法 取整
- 解决IIS Express 80端口被占用的情况
- iPhone 上拨号键盘的发音规律
- cowboy使用restful的例子
- C# 平时碰见的问题【3】
- [转载] FFmpeg 错误 C4996: ‘avcodec_alloc_frame’: 被声明为已否决 解决方法
- MySQL通配符过滤
- windows时间同步出错
- ActiveMQ之selector的用法
- UIColor的用法
- 二、JSP的3个编译指令，7个动作指令，9个内置对象
- ios后台程序持续运行方法
- 综合（奇技淫巧）：HDU 5118 GRE Words Once More!
- 应用SecureCRT（发送接收文件）