Big Hippo / Little Elephant and Balloons

• Problem 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.

• Test Case 1

  
  Input (stdin)

  2
  
  2 2
  
  1 4
  
  2 7
  
  2 1
  
  1 4
  
  2 7
  
  

  Expected Output

  11.000000000
  
  7.333333333

• Test Case 2

  
  Input (stdin)

  2 2
  
  1 7
  
  2 7
  
  3 1
  
  1 4
  
  2 2
  
  

  Expected Output

  3.333333333
  
  2.000000000

Solution

#include<stdio.h>

long long int data[41][2];

long long int Answer(int k,int num);

int main ()

{

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

    long long int answer;

    scanf("%d",&t);

    while(t--)

    {

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

answer=0;

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

  data[i][0]=data[i][1]=0;

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

{

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

    data[c][0]+=p;

    data[c][1]++;

}

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

  if(data[i]>0)

    answer+=data[i][0]*(1<<(data[i][1]-1))*Answer(m-1,i);

printf("%.9lf\n",(double)answer/Answer(m,0));

    }

    return 0;

}

long long int Answer(int k, int num)

{

    long long int answer=0,e[41][41],v[41];

    int i,j=1,tot=0;

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

      if (data[i][0]>0&&i!=num)

      {

  v[j++]=(1<<data[i][1])-1;

  tot++;

      }

    for(i=0;i<tot+1;i++)

      e[i][0]=1;

    for (i=0;i<tot+1;i++)

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

if (j>i)

  e[i][j]=0;

else

  e[i][j]=e[i-1][j]+e[i-1][j-1]*v[i];

    for (i=k;i<=tot;i++)

      answer+=e[tot][i];

    return answer;

}