#1003. 博宝自动机

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Non_User8

题目描述

众所周知,博宝是一只大鹅,如图。

在2023年四川省程序设计大赛的前一天,博宝被困在了娃娃机里。恰好被彬哥和鑫宝遇到了,于是彬哥和鑫宝打算解救博宝。

但是娃娃机真的太坑了!坑了重庆邮电大学ACM集训队合计100多元,于是彬哥和鑫宝发明了博宝自动机,专门用来解救博宝。

博宝自动机的运行方式如下: 所有的博宝躺在娃娃机里有三种情况

第一种:鹅头向上,显然此时抓取的概率最低
第二种:鹅头向下,此时身体向上最好抓
第三种:鹅头侧躺

三种情况的抓取成功率分别为 a、b、c

然后博宝自动机一共有两种操作

操作1:博宝自动机自动360°摇用拉杆,然后在摆幅最大的时候按下抓取按钮
。使所有的博宝的状态改变,使得所有鹅头向上的博宝变得鹅头侧躺,
所有鹅头向下的博宝变得鹅头侧躺,所有鹅头侧躺的博宝有一半的几率变得变得鹅头向上、一半的几率变得鹅头向下。
操作2: 博宝自动机会直接开抓,随机选择一只博宝抓取

彬哥和鑫宝想知道,最少进行多少次操作1之后进行一次操作2会让抓取到的博宝数量期望最大,最大为多少?

输入格式

第一行输入两个正整数n和m代表娃娃机中有n行,每行有m只博宝。

接下来输入n行,每行输入m个正整数,代表博宝当前的状态。

如果输入的是1代表初始鹅头向上,输入2代表初始鹅头向下,输入3代表初始鹅头侧躺

接下来一行输入三个小数a、b、c代表三种情况下抓取博宝的概率。

输出格式

第一行输出一个正整数代表最少需要的操作1的次数

第二行输出一个小数代表抓取到的博宝数量期望的最大值,保留6位小数

样例

样例输入1

1 1
1
1.00 0 0

样例输出1

0
1.000000

样例输入2

3 3
1 3 1
3 1 3
1 1 1
0.25 0.12 0.55

样例输出2

1
0.428333

数据范围与提示

对于操作1: 例如现在博宝们的状态是

->,<- 会变为 ^,v

即两个侧躺的博宝一个变成向上一个向下。

v,^ 会变为 <-、<- 、即不论向上还是向下的博宝都变成侧躺状态。 (^表示鹅头向上,v表示鹅头向下)