← 返回题目列表

Codeforces · 995/D

D. 游戏

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

艾伦和贝西正在玩一个简单的数字游戏。他们都知道一个函数 $$$f: \{0, 1\}^n \to \mathbb{R}$$$, i. e.该函数接受 $$$n$$$ 二进制参数并返回一个实值。游戏开始时,变量$$$x_1、x_2、\dots、x_n$$$ 均设置为$$$-1$$$。每一轮,艾伦或贝西中的一个以相同的概率采取行动。移动包括选择 $$$i$$$ 使得 $$$x_i = -1$$$ 并将 $$$x_i 设置为 0$$$ 或将 $$$x_i 设置为 1$$$。

$$$n$$$ 轮后,所有变量均已设置,游戏值解析为 $$$f(x_1, x_2, \dots, x_n)$$$。艾伦想要最大化游戏价值,而贝西想要最小化它。

你的目标是帮助艾伦和贝西找到预期的游戏价值!不过,他们会玩 $$$r+1$$$ 次,因此在每场游戏之间,$$$f$$$ 的一个值会发生变化。换句话说,在 $$$i$$$ 和 $$$i+1$$$ 之间,对于 $$$1 \le i \le r$$$,$$$f(z_1, \dots, z_n) \ 到 g_i$$$ 对于某些 $$$(z_1, \dots, z_n) \in \{0, 1\}^n$$$。你要在每次改变开始时和之后找到预期的游戏价值。

输入

第一行包含两个整数 $$$n$$$ 和 $$$r$$$ ($$$1 \le n \le 18$$$, $$$0 \le r \le 2^{18}$$$)。

下一行包含 $$$2^n$$$ 整数 $$$c_0, c_1, \dots, c_{2^n-1}$$$ ($$$0 \le c_i \le 10^9$$$),表示 $$$f$$$ 的初始值。更具体地说,$$$f(x_0, x_1, \dots, x_{n-1}) = c_x$$$,如果 $$$x = \overline{x_{n-1} \ldots x_0}$$$ 为二进制。

接下来的 $$$r$$$ 行包含两个整数 $$$z$$$ 和 $$$g$$$ ($$$0 \le z \le 2^n - 1$$$, $$$0 \le g \le 10^9$$$)。如果 $$$z = \overline{z_{n-1} \dots z_0}$$$ 为二进制,则意味着将 $$$f(z_0, \dots, z_{n-1}) \ 设置为 g$$$。

输出

打印 $$$r+1$$$ 行,其中第 $$$i$$$ 表示第 $$$i$$$ 轮中游戏 $$$f$$$ 的价值。您的答案的绝对或相对误差必须在 $$$10^{-6}$$$ 以内。

正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。如果 $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$,则认为您的答案是正确的。

示例

输入 #1

2 2
0 1 2 3
2 5
0 4

输出 #1

1.500000
2.250000
3.250000

输入 #2

1 0
2 3

输出 #2

2.500000

输入 #3

2 0
1 1 1 1

输出 #3

1.000000

注意

考虑第二个测试用例。如果 Allen 先走,他会将 $$$x_1 \ 设置为 1$$$,因此最终值将是 $$$3$$$。如果 Bessie 先走,那么她会将 $$$x_1 设置为 0$$$,因此最终值将为 $$$2$$$。因此答案是$$$2.5$$$。

在第三个测试用例中,无论 Allen 和 Bessie 的表现如何,游戏价值始终为 $$$1$$$。