The secret code

Input file: stdinOutput file: stTime limit: 1 sec

Memory limit: 256 Mb

After returning from the trip, Alex was unpleasantly surprised: his porch door had a new combination lock. Alex

can not get into his house! Code lock contains N disks, each of which can be in one of M positions. There

is only one correct position. Alex thoroughly inspected discs and by fingerprints and scratches determined the

probability of each position for each disk. Now Alex has K attempts to guess the correct code: if he fails, his

vigilant neighbors will call the police, and Alex will have a hard time persuading cops that he is not a thief, but

tried to get home. Help Alex to calculate the maximum probability of getting home, not to the police.

Limit

1 ≤ N ≤ 100

1 ≤ M ≤ 20

1 ≤ K ≤ 100

0 ≤ P ij ≤ 100

Input

The first line of input file contains three integers: N, M Рё K.

Next N lines contain M integers each: j-th number of the i-th line (P ij ) — the probability of a situation where

i-th disc’s correct position is j. Given that

P M

j=1 P ij

= 100.

Output

Print a single number — Alex’s chances to guess the correct code in time. Output result should have an absolute

percentage error not grater than 10 −7 .

Example

stdin

2 2 1

50 50

10 90

3 5 4

10 15 20 25 30

1 2 3 4 90

100 0 0 0 0

stdout

0.45

0.81

 

题目大意：

　　　n个数列，每个数列取一个数，得到这些数的乘积，求前k个最大的乘积。

 

多谢syx的指导！

解题思路：

　　对每个数列排序后。

　　首先，第一大的自然是所有数列最大值乘积。

　　接着，将最大乘积加到ans上，然后将这个乘积能够达到的所有下一个状态均加入优先队列中。至于保存状态，每个状态只需保存其在每个数列的取到第几个数的指针即可，显然下一个状态是在该状态之后，并且出现在某一个指针向后移位。故将所有下一个状态加入优先队列。

　　然后，当找到第k个或者是空队列时退出循环，否则返回上一步。

　　最后，输出答案。

 

实现方法，直接使用STL中的priority_queue，若数据量加大，可惜优先队列不能删除尾节点，不过可利用最大最小堆保存前k个即可。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include