T-shirt

题意翻译

## 题目描述 你将在CodeForces的一个$n$人团队实习，n个工程师由1到$n$编号。你决定给每个工程师一个纪念品：一件来自你的国家的T恤（T恤在CodeForces很受欢迎）。不幸的是，你不知道$n$个工程师各自衣服的尺寸。一共有1到m共m种不同的尺寸，并且每个工程师只适合一个尺寸。 你不知道每个工程师的尺寸，所以你询问你的朋友Gerald。很遗憾，他也不知道每个工程师的尺寸，但他知道对于第$i$个工程师，适合第j种T恤的概率。 最后你带来了$n$件T恤（这$n$件T恤可以是任意组合，你也可以带多件同样尺寸的衣服），在你准备T恤的时候并不知道每个工程师的尺寸，所以你只能根据Gerald提供的概率决定你所带的T恤。 你的任务是最大化收到适合自己的衣服的工程师数量的期望值。 当你到达办公室后，你会询问每个工程师他适合的T恤的尺寸，如果你有那个尺寸的衣服，你就会给他一件，否则就不给他T恤。你会从$1$号问起，一直问到$n$号 --- ## 输入输出格式 ### 输入格式 第一行为两个用空格分开的整数n和m（$1<=n<=3000$,$1<=m<=300$)，分别代表工程师数量和衣服尺寸数量 接下来有$n$行，每行$m$个空格分开的整数，第$i$行第$j$个数字代表第$i$个工程师适合第$j$种T恤的概率。每个整数在$1$到$1000$之间。实际上的概率应为每个整数除以1000。 保证对于每个工程师适合每种T恤的概率之和为$1$。 ### 输出格式 输出一行，一个实数代表收到T恤的工程师数量的最大期望值。允许最大误差为$10^{-9}$。 感谢@LJZ_C 提供的翻译

题目描述

You are going to work in Codeforces as an intern in a team of $ n $ engineers, numbered $ 1 $ through $ n $ . You want to give each engineer a souvenir: a T-shirt from your country (T-shirts are highly desirable in Codeforces). Unfortunately you don't know the size of the T-shirt each engineer fits in. There are $ m $ different sizes, numbered $ 1 $ through $ m $ , and each engineer will fit in a T-shirt of exactly one size. You don't know the engineers' exact sizes, so you asked your friend, Gerald. Unfortunately, he wasn't able to obtain the exact sizes either, but he managed to obtain for each engineer $ i $ and for all sizes $ j $ , the probability that the size of the T-shirt that fits engineer $ i $ is $ j $ . Since you're planning to give each engineer one T-shirt, you are going to bring with you exactly $ n $ T-shirts. For those $ n $ T-shirts, you can bring any combination of sizes (you can bring multiple T-shirts with the same size too!). You don't know the sizes of T-shirts for each engineer when deciding what sizes to bring, so you have to pick this combination based only on the probabilities given by your friend, Gerald. Your task is to maximize the expected number of engineers that receive a T-shirt of his size. This is defined more formally as follows. When you finally arrive at the office, you will ask each engineer his T-shirt size. Then, if you still have a T-shirt of that size, you will give him one of them. Otherwise, you don't give him a T-shirt. You will ask the engineers in order starting from engineer $ 1 $ , then engineer $ 2 $ , and so on until engineer $ n $ .

输入输出格式

输入格式

The first line contains two space-separated integers $ n $ and $ m $ $ (1<=n<=3000,1<=m<=300) $ , denoting the number of engineers and the number of T-shirt sizes, respectively. Then $ n $ lines follow, each line contains $ m $ space-separated integers. The $ j $ -th integer in the $ i $ -th line represents the probability that the $ i $ -th engineer fits in a T-shirt of size $ j $ . Each probability will be given as an integer between $ 0 $ and $ 1000 $ , inclusive. The actual probability should be calculated as the given number divided by $ 1000 $ . It is guaranteed that for any engineer, the sum of the probabilities for all $ m $ T-shirts is equal to one.

输出格式

Print a single real number denoting the maximum possible expected number of engineers that will receive a T-shirt. For the answer the absolute or relative error of $ 10^{-9} $ is acceptable.

输入输出样例

输入样例 #1

2 2
500 500
500 500

输出样例 #1

1.500000000000

输入样例 #2

3 3
1000 0 0
1000 0 0
0 1000 0

输出样例 #2

3.000000000000

输入样例 #3

1 4
100 200 300 400

输出样例 #3

0.400000000000

说明

For the first example, bring one T-shirt of each size. With $ 0.5 $ chance, either both engineers fit inside T-shirts of size $ 1 $ or both fit inside T-shirts of size $ 2 $ . With the other $ 0.5 $ chance, one engineer fits inside a T-shirt of size $ 1 $ and the other inside a T-shirt of size $ 2 $ . If the first is true, the number of engineers that receive a T-shirt is one. If the second is true, the number of such engineers is two. Hence, the expected number of engineers who receive a T-shirt is $ 1.5 $ . This is maximum possible expected number of engineers for all sets of T-shirts. For the second example, bring two T-shirts of size $ 1 $ and one T-shirt of size $ 2 $ . This way, each engineer will definitely receive a T-shirt of his size. For the third example, bring one T-shirt of size $ 4 $ .