Little Elephant and Balloons

Description:

The Little Elephant from the Zoo of Lviv is going to the Birthday Party of the Big Hippo tomorrow. Now he wants to prepare a gift for the Big Hippo. He has N balloons, numbered from 1 to N. The i-th balloon has the color Ci and it costs Pi dollars. The gift for the Big Hippo will be any subset (chosen randomly, possibly empty) of the balloons such that the number of different colors in that subset is at least M. Help Little Elephant to find the expected cost of the gift. Input The first line of the input contains a single integer T - the number of test cases. Ttest cases follow. The first line of each test case contains a pair of integers N and M. The next N lines contain N pairs of integers Ci and Pi, one pair per line. Output In T lines print T real numbers - the answers for the corresponding test cases. Your answer will considered correct if it has at most 10^-6 absolute or relative error. Constraints 1 ≤ T ≤ 40 1 ≤ N, Ci≤ 40 1 ≤ Pi ≤ 1000000 0 ≤ M ≤ K, where K is the number of different colors in the test case. Example Input: 2 2 2 1 4 2 7 2 1 1 4 2 7 Output: 11.000000000 7.333333333

Program :

#include<stdio.h>


int colours[42][42]={0},count_color;

unsigned long long int sum[42]={0},nf[42],total_subsets[42][42][42],tempans,denom;

double ans;


void sumi(int i)

{

int k=0,j=0;

unsigned long long int appears=1;

while(colours[i][j]!=0)

{ k++;j++;}

j=k-1;

appears=1<<j;

nf[i]=(1<<k) - 1;

//printf("%d",appears);

for(j=0;j<k;j++)

{ sum[i]=sum[i]+(colours[i][j]*appears);

//printf("sum[%d]=%llu",i,sum[i]);

}

}


void constructnf()

{

int i,j,find=0;

total_subsets[0][0][0]=1;

//printf("i=%d:\n\n\n\n",0);

i=1;

for(find=0;find<41;find++)

   {

   if(nf[find]>0)

              {

           

           {

                total_subsets[0][i][0]=1;

            for(j=1;j<=i;j++)

         {

 total_subsets[0][i][j]=(total_subsets[0][i-1][j-1]*nf[find])+total_subsets[0][i-1][j];

// printf("%d ",total_subsets[0][i][j]);

}

// printf("\n");

  i++;

   }

}

}

//printf("\n\n\n\n\n");

}


void leaveconstruct(int y)

{

unsigned long long int nftemp[42]={0};

int j,k=0,i,find;

//printf("i=%d:\n\n\n\n",y);

for(j=0;j<42;j++)

{

if(j!=y)

nftemp[j]=nf[j];

}

k=j-1;

total_subsets[y][0][0]=1;

i=1;

for(find=0;find<41;find++)

   {

   if(nftemp[find]>0)

              {

           

           {

                total_subsets[y][i][0]=1;

            for(j=1;j<=i;j++)

         {

 total_subsets[y][i][j]=(total_subsets[y][i-1][j-1]*nf[find])+total_subsets[y][i-1][j];

// printf("%d ",total_subsets[y][i][j]);

}

// printf("\n");

  i++;

   }

}

}

//printf("\n\n\n\n\n");

}

void reset()

{

int i,j,k;

for(i=0;i<42;i++)

{

sum[i]=0;

nf[i]=0;

};

for(i=0;i<42;i++)

{

for(j=0;j<42;j++)

{

colours[i][j]=0;

for(k=0;k<42;k++)

total_subsets[i][j][k]=0;

}

}

tempans=0;

denom=0;

count_color=0;

}


int main()

{

int t,n,m,c,p,i,j,flag;

unsigned long long int a;

scanf("%d",&t);

while(t--)

{

reset();

flag=0,denom=0;

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

count_color=0;

for(i=0;i<n;i++)

{

scanf("%d%d",&c,&p);

if(colours[c][0]==0)

   count_color=count_color+1;

j=0;

while(colours[c][j]!=0)

j++;

colours[c][j]=p;

}

if(count_color<m)

printf("0\n");

else{

for(i=1;i<=40;i++)

{

if(colours[i][0]!=0)

{ sumi(i);

//printf("i=%d sum[i]=%llu",i,sum[i]);

}

}

      constructnf();

  for(i=0;i<42;i++)

  {

       if(sum[i]>0)

   leaveconstruct(i);

  }

  if(m==0)

  { flag=1;m=1;}

  tempans=0;

  for(i=m;i<=count_color;i++)

  {

 

  for(j=0;j<41;j++)

  {

  if(sum[j]>0)

  {

                 tempans=tempans+(sum[j] * total_subsets[j][count_color-1][i-1]);

 //printf("tempans=%llu",tempans);

  }

  }

   denom=denom+total_subsets[0][count_color][i];

  }

  if(flag==1)

  denom++;

  ans=(double)tempans/denom;

 //printf("tempans=%llu denom=%llu",tempans,denom);

 printf("%f\n",ans);

  //printf("ans= %f\n",ans);

}

}

return 0;

}