# Baby Coins

## Description

Baby 今天清点自己的百宝箱啦，箱子里有 n 种硬币，硬币的面值分别是：val[1]，val[2]，…，val[n]，每种面值的硬币都恰好有 2 个。Baby 实在闲的太无聊了，他想从他所拥有的硬币中选出若干个，使得面值之和为 k。那么他的目标能否实现呢 ~

## Sample Input

2 2 10 3 4 3 9 1 2 10

## Sample Output

Case 1: Yes Case 2: No

//
//  main.cpp
//  1001
//
//  Created by Edwin on 2018/12/8.
//
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0×3f3f3f3f  //0×7ffffff
#define EPS 1e-8
#define pb push_back
#define maxn 20000+10
#define PI acos(-1.0)
using namespace std;
int pop1,pop2;
ll val[30];
ll tot1[maxn];
ll tot2[maxn];
void dfs1(ll get,int l,int r)
{
if(l>r) {tot1[pop1++]=0;return;}
for(int i=0;i<=2;i++)
{
if(l==r)
tot1[pop1++]=get+i*val[l];
else
dfs1(get+i*val[l],l+1,r);
}
return;
}
void dfs2(ll get,int l,int r)
{
if(l>r) {tot2[pop2++]=0;return;}
for(int i=0;i<=2;i++)
{
if(l==r)
tot2[pop2++]=get+i*val[l];
else
dfs2(get+i*val[l],l+1,r);
}
return;
}
int main()
{
int test=0;
int n,k,flag;
ll sum;
while(~scanf("%d",&test))
{
for(int p=1;p<=test;p++)
{
//memset(val,0,sizeof(val));
//memset(tot1,0,sizeof(tot1));
//memset(tot2,0,sizeof(tot2));
flag=0;sum=0;
pop1=pop2=0;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
scanf("%lld",&val[i]),sum+=val[i];
if(sum*2<k)
{
printf("Case %d: No\n",p);continue;
}
//sort(val,val+n);
dfs1(0,0,n/2-1);//枚举前半面值
dfs2(0,n/2,n-1);//枚举后半面值
sort(tot1,tot1+pop1);
sort(tot2,tot2+pop2);
long n1=unique(tot1, tot1+pop1)-tot1;
long n2=unique(tot2, tot2+pop2)-tot2;

for(int i=0;i<n1&&tot1[i]<=k&&!flag;i++)
{
//if(i!=pop1-1&&tot1[i]==tot1[i+1])continue;
if(binary_search(tot2, tot2+n2, k-tot1[i])){flag=1;break;}
}
if(flag) printf("Case %d: Yes\n",p);
else printf("Case %d: No\n",p);
}
}
return 0;
}


0 评论