NC14623. Piglet treasure hunt Series 3
描述
Once there was a pig, which was very fond of treasure hunting. The last treasure hunt he bring back a full package of diamonds, which too delight to fall asleep for a few days.
But there are too many diamonds, and it has new troubles. It wants to get some diamonds sold for cash to buy its girlfriend pretty things. The price of a diamond is proportional to its weight, the heavier the diamond, the greatest price it worth. So he wants to know the accurate weight of some diamonds going to sell.
Poor it only has an old balance, and the balance has no scale. You can only see which side of the balance is heavier, or both side have the same weight. It has N weights with different kilogram, and there are Ci for each kinds of weight.
To simplify the problem, the kilogram of all weight and all the diamonds are integer.
M diamonds is planning to be sold, the diamond merchant told the pig the ith diamond weighs wi kg, you know, businesses may misrepresent the weight, and maybe the actual weight of this diamond is not wi kg and the merchant chart it. So the pig needs to know the exact weight of each diamond. That is to say, you can puts any weights you want and the diamond need to be measure on both side of the balance and know which side is heavier in this state. If you can figure out the exact weight of this diamond through the results, then you output an “Yes”, or you output an “No” means you can’t sure the exact weigh of this diamond.
It finds you smart to tell the answer.
输入描述
Multiple groups of test case .(no more than 100 groups. )
The first line of each test case contains two numbers N and M (0<=N<=20,0<=M<=1000), represents there is N kind of weigh of different kilogram and M diamonds, respectively. Stop the program when N and M are both 0.
Next N lines, each line has two integer Wi and Ci (1<=Wi<=500,1<=Ci<=10). The ith kind of weigh is Wi kg, and the number of this kind is Ci .
Next M line, each line has an integer Ai, representing the dealer's diamond weight is Ai kg.
输出描述
For each test case, output the M lines. Each line output either ‘Yes’ or ‘No’, representing if it can accurately know the ith diamond’s weigh.
示例1
输入:
3 3 1 1 4 1 5 1 1 3 7 0 0
输出:
Yes Yes No
说明:
For a trader who reports a diamond with a weight of 1kg, a 1kg can be placed on the left side of the balance, and the diamond is placed on the right side, and the balance is flat at the right time. It is determined that the exact weight of the diamond is 1kg, and the output is Yes.
For a trader who reports a diamond with a weight of 3kg, a 1kg weight and a diamond can be placed on the left side of the balance, and the weight of 4kg on the right is placed on the right side, and the balance is flat at the right time. It is determined that the exact weight of the diamond is 3kg, and the output is Yes.
For the merchant to report a diamond with a weight of 7kg, if the 4kg and 5kg weights are placed on the left side, the diamond is placed on the right side, and the balance tends to the left. If you put 1kg and 5kg weights on the left side, diamonds on the right side, the scales tend to the right side. In any case, it can't be determined whether the diamond's exact weight is 7kg, so the output is No.
C++14(g++5.4) 解法, 执行用时: 32ms, 内存消耗: 4452K, 提交时间: 2020-04-01 17:14:47
#include<bits/stdc++.h>
#define N 1000001
using namespace std;
int n,m,f[N];
inline void solve()
{
memset(f,0,sizeof f);
f[0]=1;
int sum=0;
int x,y;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
while(y--)
{
sum+=x;
for(int j=sum;j>=x;j--)
f[j]|=f[j-x];
}
}
while(m--)
{
scanf("%d",&x);
int pd=0;
for(int j=sum;j>=x;j--)
{
if(f[j]&f[j-x])
{
pd=1;
break;
}
if(j-x>0&&f[j-x-1]&&f[j-x+1]&&f[j])
{
pd=1;
break;
}
}
if(pd) puts("Yes");
else
puts("No");
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
if(!n&&!m) return 0;
solve();
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 27ms, 内存消耗: 4236K, 提交时间: 2020-03-31 13:12:02
#include<bits/stdc++.h>
#define N 1000001
using namespace std;
int n,m,f[N];
inline void solve()
{
memset(f,0,sizeof f);
f[0]=1;
int sum=0;
int x,y;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
while(y--)
{
sum+=x;
for(int j=sum;j>=x;j--)
f[j]|=f[j-x];
}
}
while(m--)
{
scanf("%d",&x);
int pd=0;
for(int j=sum;j>=x;j--)
{
if(f[j]&f[j-x])
{
pd=1;
break;
}
if(j-x>0&&f[j-x-1]&&f[j-x+1]&&f[j])
{
pd=1;
break;
}
}
if(pd) puts("Yes");
else
puts("No");
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
if(!n&&!m) return 0;
solve();
}
return 0;
}