Description

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

Input

每一组数据第一行都包含两个数字 n(n≤18)，k(1≤k≤109)。n 代表箱子中所包含的硬币种数，k 代表 Baby 需要组成的金钱数额。接下来的一行代表 val[1]，val[2]，……，val[n]。(1≤val[i]≤ 107)

Output

如果Baby能组成金钱数额k,请输出Yes，否则输出No。

Sample Input

2 2 10 3 4 3 9 1 2 10

Sample Output

Case 1: Yes Case 2: No

题解：Meet in the Middle算法，高效搜索区间，一般应用于广搜（BFS）；这道题先分块枚举所有可能组成的面值，再加起来看能否组合成k；

//
//  main.cpp
//  1001
//
//  Created by Edwin on 2018/12/8.
//  Copyright © 2018 Edwin. All rights reserved.
//
#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;
}