← 返回题目列表

AtCoder · abc313_f

I. 翻转机

中文机器翻译题面 查看原题

分数: 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 将执行以下过程。

  1. 选择一组 S 由整数组成 1 通过 M.
  2. 对于中的每个元素 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