#include <stdio.h>
#define bool short
#define true 1
#define false 0
bool subset[23][10009]={false};
short set[23];
void quicksort(short first,short last){
short pivot,j,temp,i;
if(first<last){
pivot=first;
i=first;
j=last;
while(i<j){
while(set[i]>=set[pivot]&&i<last)
i++;
while(set[j]<set[pivot])
j--;
if(i<j){
temp=set[i];
set[i]=set[j];
set[j]=temp;
}
}
temp=set[pivot];
set[pivot]=set[j];
set[j]=temp;
quicksort(first,j-1);
quicksort(j+1,last);
}
}
bool isSubsetSum(short n, short sum)
{
short i,j;
for (i = 0; i <= n; i++)
subset[i][0] = true;
for (i = 1; i <= sum; i++)
subset[0][i] = false;
for(i=1;i<=n;i++)
{
for(j=1;j<=sum;j++)
{
subset[i][j]=subset[i-1][j];
if( j>= set[i] )
if(subset[i-1][j-set[i]]==true )
subset[i][j]=true;
}
}
return subset[n][sum];
}
void findnum(short row,short col)
{
short num=0;
while(col>0 && row>=0)
{
if( subset[row-1][col]==true && row>0)
row--;
else if( subset[row-1][col-set[row]] ==true && row>0 &&col>=set[row]) {
num++;
col=col-set[row];row--;
}
else
break;
}
}
int main()
{
int t,n,k,i;
while(t--)
{
set[0]=0;
for(i=1;i<=n;i++)
quicksort(1,n);
if (isSubsetSum(n,k)==true)
findnum(n,k);
else
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CgojZGVmaW5lIGJvb2wgc2hvcnQKI2RlZmluZSB0cnVlIDEKI2RlZmluZSBmYWxzZSAwCgpib29sIHN1YnNldFsyM11bMTAwMDldPXtmYWxzZX07CnNob3J0IHNldFsyM107IAoKdm9pZCBxdWlja3NvcnQoc2hvcnQgZmlyc3Qsc2hvcnQgbGFzdCl7CiAgICBzaG9ydCBwaXZvdCxqLHRlbXAsaTsKCiAgICAgaWYoZmlyc3Q8bGFzdCl7CiAgICAgICAgIHBpdm90PWZpcnN0OwogICAgICAgICBpPWZpcnN0OwogICAgICAgICBqPWxhc3Q7CgogICAgICAgICB3aGlsZShpPGopewogICAgICAgICAgICAgd2hpbGUoc2V0W2ldPj1zZXRbcGl2b3RdJiZpPGxhc3QpCiAgICAgICAgICAgICAgICAgaSsrOwogICAgICAgICAgICAgd2hpbGUoc2V0W2pdPHNldFtwaXZvdF0pCiAgICAgICAgICAgICAgICAgai0tOwogICAgICAgICAgICAgaWYoaTxqKXsKICAgICAgICAgICAgICAgICB0ZW1wPXNldFtpXTsKICAgICAgICAgICAgICAgICAgc2V0W2ldPXNldFtqXTsKICAgICAgICAgICAgICAgICAgc2V0W2pdPXRlbXA7CiAgICAgICAgICAgICB9CiAgICAgICAgIH0KCiAgICAgICAgIHRlbXA9c2V0W3Bpdm90XTsKICAgICAgICAgc2V0W3Bpdm90XT1zZXRbal07CiAgICAgICAgIHNldFtqXT10ZW1wOwogICAgICAgICBxdWlja3NvcnQoZmlyc3Qsai0xKTsKICAgICAgICAgcXVpY2tzb3J0KGorMSxsYXN0KTsKCiAgICB9Cn0KCmJvb2wgaXNTdWJzZXRTdW0oc2hvcnQgbiwgc2hvcnQgc3VtKQp7CiAgICBzaG9ydCBpLGo7CiAgICBmb3IgKGkgPSAwOyBpIDw9IG47IGkrKykKICAgICAgc3Vic2V0W2ldWzBdID0gdHJ1ZTsKIAogICAgZm9yIChpID0gMTsgaSA8PSBzdW07IGkrKykKICAgICAgc3Vic2V0WzBdW2ldID0gZmFsc2U7CiAKICAgIGZvcihpPTE7aTw9bjtpKyspCiAgICB7CiAgICAgICBmb3Ioaj0xO2o8PXN1bTtqKyspCiAgICAgICB7CiAgICAgICAgICBzdWJzZXRbaV1bal09c3Vic2V0W2ktMV1bal07ICAKICAgICAgICAgIGlmKCBqPj0gc2V0W2ldICkKICAgICAgICAgICAgaWYoc3Vic2V0W2ktMV1bai1zZXRbaV1dPT10cnVlICkgCiAgICAgICAgICAgICAgc3Vic2V0W2ldW2pdPXRydWU7CiAgICAgICB9CiAgIH0gICAKcmV0dXJuIHN1YnNldFtuXVtzdW1dOwp9Cgp2b2lkIGZpbmRudW0oc2hvcnQgcm93LHNob3J0IGNvbCkKewogICBzaG9ydCBudW09MDsKICAgd2hpbGUoY29sPjAgJiYgcm93Pj0wKQogICB7CiAgICAgICBpZiggc3Vic2V0W3Jvdy0xXVtjb2xdPT10cnVlICYmIHJvdz4wKSAgICAgICAgIAogICAgICAgICByb3ctLTsKICAgICAgICAgIAogICAgICAgZWxzZSBpZiggc3Vic2V0W3Jvdy0xXVtjb2wtc2V0W3Jvd11dID09dHJ1ZSAmJiByb3c+MCAmJmNvbD49c2V0W3Jvd10pIHsKICAgICAgICAgICAgICAgbnVtKys7ICAgCiAgICAgICAgICAgICAgIGNvbD1jb2wtc2V0W3Jvd107cm93LS07CiAgICAgICAgIH0KICAgICAgIGVsc2UKICAgICAgICAgIGJyZWFrOyAKICAgICAgIAogICB9CiAgICAgICAgCnByaW50ZigiJWRcbiIsbnVtKTsgCgp9CgogCmludCBtYWluKCkKewogIGludCAgdCxuLGssaTsKICBzY2FuZigiJWQiLCZ0KTsKICB3aGlsZSh0LS0pCiAgewogICAgICBzY2FuZigiJWQlZCIsJm4sJmspOwogICAgICBzZXRbMF09MDsgCiAgICAgIGZvcihpPTE7aTw9bjtpKyspCiAgICAgICAgIHNjYW5mKCIlZCIsJnNldFtpXSk7IAogICAgICBxdWlja3NvcnQoMSxuKTsKICAgICAgaWYgKGlzU3Vic2V0U3VtKG4sayk9PXRydWUpCiAgICAgICAgIGZpbmRudW0obixrKTsKICAgICAgZWxzZQogICAgICAgICBwcmludGYoImltcG9zc2libGVcbiIpOwogIH0KICByZXR1cm4gMDsKfQ==