分数: 625 点
问题陈述
有 N 卡片编号 1 通过 N。 卡片的每一面都写有一个整数;卡 i 有 A_i 在其正面和 B_i 在它的背面。 最初,所有卡片均面朝上。
有 M 机器编号 1 通过 M。 机器 j 有两个(不一定不同)整数 X_j 和 Y_j 之间 1 和 N。 如果你打开机器电源 j, 它翻转卡片 X_j 的概率为 \frac{1}{2},然后翻转卡片 Y_j 剩余概率为 \frac{1}{2}。 这个概率对于每次加电都是独立的。
Snuke 将执行以下过程。
- 选择一组 S 由整数组成 1 通过 M.
- 对于中的每个元素 S 按升序,用该编号启动机器。
Snuke 的可能选择 S,找出程序后写在卡片正面朝上的整数之和的最大期望值。
约束
- 1\leq N \leq 40
- 1\leq M \leq 10^5
- 1\leq A_i,B_i \leq 10^4
- 1\leq X_j,Y_j \leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 \vdots A_N B_N X_1 Y_1 \vdots X_M Y_M
输出
打印答案。 如果与真实值的绝对或相对差异最多为,则您的输出被认为是正确的 10^{-6}.
示例输入 1
3 1 3 10 10 6 5 2 1 2
示例输出 1
19.500000
If S 被选择为空集,没有机器通电,因此在该过程之后写在卡片正面朝上的整数的期望总和为 3+10+5=18.
If S 被选择为 \lbrace 1 \rbrace,机器 1 已通电。
- 如果卡 X_1 = 1 被翻转,程序执行后卡片正面朝上写入的整数的期望总和为 10+10+5=25.
- 如果卡 Y_1 = 2 被翻转,程序执行后卡片正面朝上写入的整数的期望总和为 3+6+5=14.
因此,预期值为 \frac{25+14}{2} = 19.5.
因此,在该过程之后,写在卡片正面朝上的整数之和的最大期望值为 19.5.
示例输入 2
1 3 5 100 1 1 1 1 1 1
示例输出 2
100.000000
不同的机器可能有相同的 (X_j,Y_j).
示例输入 3
8 10 6918 9211 16 1868 3857 8537 3340 8506 6263 7940 1449 4593 5902 1932 310 6991 4 4 8 6 3 5 1 1 4 2 5 6 7 5 3 3 1 5 3 1
示例输出 3
45945.000000