fork(1) download
copy 
  1. #include <stdio.h>
  2.  
  3. #define bool short
  4. #define true 1
  5. #define false 0
  6.  
  7. bool subset[23][10009]={false};
  8. short set[23]; 
  9.  
  10. void quicksort(short first,short last){
  11.     short pivot,j,temp,i;
  12.  
  13.      if(first<last){
  14.          pivot=first;
  15.          i=first;
  16.          j=last;
  17.  
  18.          while(i<j){
  19.              while(set[i]>=set[pivot]&&i<last)
  20.                  i++;
  21.              while(set[j]<set[pivot])
  22.                  j--;
  23.              if(i<j){
  24.                  temp=set[i];
  25.                   set[i]=set[j];
  26.                   set[j]=temp;
  27.              }
  28.          }
  29.  
  30.          temp=set[pivot];
  31.          set[pivot]=set[j];
  32.          set[j]=temp;
  33.          quicksort(first,j-1);
  34.          quicksort(j+1,last);
  35.  
  36.     }
  37. }
  38.  
  39. bool isSubsetSum(short n, short sum)
  40. {
  41.     short i,j;
  42.     for (i = 0; i <= n; i++)
  43.       subset[i][0] = true;
  44.  
  45.     for (i = 1; i <= sum; i++)
  46.       subset[0][i] = false;
  47.  
  48.     for(i=1;i<=n;i++)
  49.     {
  50.        for(j=1;j<=sum;j++)
  51.        {
  52.           subset[i][j]=subset[i-1][j];  
  53.           if( j>= set[i] )
  54.             if(subset[i-1][j-set[i]]==true ) 
  55.               subset[i][j]=true;
  56.        }
  57.    }   
  58. return subset[n][sum];
  59. }
  60.  
  61. void findnum(short row,short col)
  62. {
  63.    short num=0;
  64.    while(col>0 && row>=0)
  65.    {
  66.        if( subset[row-1][col]==true && row>0)         
  67.          row--;
  68.  
  69.        else if( subset[row-1][col-set[row]] ==true && row>0 &&col>=set[row]) {
  70.                num++;   
  71.                col=col-set[row];row--;
  72.          }
  73.        else
  74.           break; 
  75.  
  76.    }
  77.  
  78. printf("%d\n",num); 
  79.  
  80. }
  81.  
  82.  
  83. int main()
  84. {
  85.   int  t,n,k,i;
  86.   scanf("%d",&t);
  87.   while(t--)
  88.   {
  89.       scanf("%d%d",&n,&k);
  90.       set[0]=0; 
  91.       for(i=1;i<=n;i++)
  92.          scanf("%d",&set[i]); 
  93.       quicksort(1,n);
  94.       if (isSubsetSum(n,k)==true)
  95.          findnum(n,k);
  96.       else
  97.          printf("impossible\n");
  98.   }
  99.   return 0;
  100. }
Success #stdin #stdout 0s 2460KB
comments (?)
stdin
copy 
3
5 4
10 9 5 3 4
3 7
1 3 2
6 16
2 4 6 2 12 16
stdout
copy 
1
impossible
1
https://ideone.com/VhYdPv
language:
C (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!