Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:256 MB

#1064. 一

统计

众所周知,小葱同学擅长计算,尤其擅长计算组合数,但这个题和组合数没什么关系。
𝑁行𝑀列的皮克敏,射杀第𝑖行第𝑗列皮克敏成功的概率为𝑝𝑖𝑗%。你的目标是使得至少一列的皮克敏死光。在你决定了射杀顺序之后,你会按照如下规则进行射杀:
1、如果当前射杀的皮克敏没有死,则之后会跳过所有对该列的射杀操作。
2、如果某次操作之后存在一列死光了,则停止射杀剩下所有的皮克敏。
如果你可以自由决定射杀的顺序,问所有顺序中期望射杀次数最少是多少。
【输入格式】
第一行两个整数𝑁, 𝑀。
接下来𝑁行𝑀列代表𝑝𝑖𝑗。
【输出格式】
一行一个五位小数代表答案。
【样例输入】
2 2
50 50
50 50
【样例输出】
2.62500
【数据规模与约定】
对于40%的数据,𝑁, 𝑀 ≤ 3。
对于另外40%的数据,𝑝𝑖𝑗 = 50。
对于100%的数据,1 ≤ 𝑁 ≤ 10,1 ≤ 𝑀 ≤ 250。