【Link】:

【Description】



KTV给你T秒的唱歌时间;

你有n首一定要唱的歌;

然后有一首很变态的歌有678s,你想在T秒结束之前唱一下这首歌;

因为这样的话,你能尽量晚地走出KTV(不会在你唱到一半的时候让你不唱了),即你最后的唱歌时间是可以超过T秒的;

告诉你n首歌的时间;

这n首歌里面任选几道唱,但必须要留一点时间唱那首变态的歌;

问你最多能唱多少首歌,然后在唱歌最多的基础上,问你最晚能什么时候走出KTV

【Solution】



如果∑a[i]<T的话,则直接输出答案n+1和∑a[i] + 678;

否则;

计算在T-1秒内,你最多能唱多少首歌（不包括那首变态的歌）;

(即最少留一秒钟开始唱那首变态的歌);

即设f[i]表示花费恰好i秒,最多能唱多少首除了那首变态的歌之外的歌;

最后逆序从T-1到0里面找下标最大(即时间)的,且f值最大的f[idx]

,输出f[idx]+1,和idx+678即可;



【NumberOf WA】



1



【Reviw】



忘记处理∑a[i] < T的情况了;



【Code】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define Open() freopen("F:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 50;

int n,t;

int a[N+20],f[N*180+10];

int main(){

    //Open();

    //Close();

    int T,kk = 0;

    scanf("%d",&T);

    while (T--){

        kk++;

        scanf("%d%d",&n,&t);

        int sum = 0;

        rep1(i,1,n){

            scanf("%d",&a[i]);

            sum+=a[i];

        }

        //f[i]代表花费时间为i,最多能唱多少首歌

        f[0] = 0;

        if (t > sum){

            printf("Case %d: %d %d\n",kk,n+1,sum + 678);

            continue;

        }

        rep1(i,1,t-1)

            f[i] = -1;

        rep1(i,1,n){

            rep2(j,t-1,a[i])

                if (f[j-a[i]]>=0)

                    f[j] = max(f[j],f[j-a[i]] + 1);

        }

        int ma = -1,idx;

        rep2(i,t-1,0)

            if (f[i]>ma){

                ma = f[i],idx = i;

            }

        //678s

        printf("Case %d: %d %d\n",kk,ma+1,idx + 678);

    }

    return 0;

}