抛硬币(qsort排序)

时间:2022-04-14 21:56:28


Description

James得到了一堆有趣的硬币,于是决定用这些硬币跟朋友们玩个小游戏。在一个N行M列的表格上,每一个第i行第j列的格子上都放有一枚James的硬币,抛该硬币正面朝上的概率为Pij,所有抛硬币事件两两之间是相互独立的。

现在,玩家在M列硬币中,从每一列里各选择1枚,共M枚,构成一组。如此重复选择N组出来,且保证被选择过的硬币不能再选。选好组之后,每组的M枚硬币各抛一次,如果都是正面朝上,则该组胜利,总分赢得1分;否则该组失败,总分不加也不减。请问,如果让你自行选择硬币的分组,游戏总得分的数学期望的最大值是多少?

Input

输入有多组数据。每组数据第一行为N和M,1≤N≤100,1≤M≤10,以空格分隔。接下来有N行,每行M个小数,表示表格中对应的Pij。

输入以N=M=0结束,这组数据不输出结果。

Output

对于每组数据,输出对应游戏总得分的数学期望的最大值,四舍五入精确至4位小数。每组数据的输出占一行。

Sample Input

2 3
1.0 1.0 1.0
0.5 0.4 0.3
0 0

Sample Output

1.0600

HINT

# include <stdio.h>
# include <stdlib.h>

# define LMAX 105
# define CMAX 15

double table[CMAX][LMAX];
double e;
int N, M;

int cmp(const double *pa, const double *pb);

int main()
{
     double tmp;
     int i, j;
    
     while (1)
     {
           scanf("%d%d", &N, &M);
           if (!M && !N) break;
           for (i = 0; i < N; ++i)
              for (j = 0; j < M; ++j)
                     scanf("%lf", &table[j][i]);
              for (j = 0; j < M; ++j)
                    qsort(table[j], N, sizeof(double), cmp);
          for (e = 0, i = 0; i < N; ++i)
          {
                 tmp = 1.0;
                 for (j = 0; j < M; ++j)
                     tmp *= table[j][i];
                 e += tmp;
          }
          printf("%.4lf\n", e);
      }
    
     return 0;
}

int cmp(const double *pa, const double *pb)
{
     if ((*pa) < (*pb)) return -1;
     else if ((*pa) > (*pb)) return 1;
     return 0;
}