305237: CF995D. Game
Memory Limit：256 MB
Time Limit：3 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Game
题意翻译
## 题意 定义一从 $n$ 位 $\texttt{01}$ 串映射到实数的函数 $f$，即 $f:\{0, 1\}^n \to \mathbb{R}$ 现有一个 $n$ 位的 $\texttt{01}$ 串，但它其中的元素都还未确定。不妨设 $x_i$ 表示该串第 $i$ 位的值（编号从 $1$ 开始），未确定的值就设为 $-1$ 又有 $\texttt{A}, \texttt{B}$ 两位玩家，他们将共执行 $n$ 次操作确定这个 $\texttt{01}$ 串；对于每次操作，将会等概率地选择 $\texttt{A}, \texttt{B}$ 其中一人，被选中的人则会选择 $x_i$ 满足 $x_i=-1$，并将其设为 $0$ 或 $1$ 其中 $\texttt{A}$ 想要最大化最终确定的串带入 $f$ 的值，$\texttt{B}$ 则想要最小化最终确定的串带入 $f$ 的值 现给出 $n$，以及对每种 $\texttt{01}$ 串带入 $f$ 得到的值；问最终确定的串的期望的带入 $f$ 得到的值 共有 $r+1$ 组询问；但对于 $r>1$ 组的询问，仅会修改一种 $\texttt{01}$ 串带入 $f$ 得到的值，其余和上一组询问完全相同 ## 输入格式 第一行两个整数 $n, r$（$1\leq n\leq 18, 0\leq r\leq 2^{18}$） 第二行 $2^n$ 个整数 $c_0, c_1, \cdots, c_{2^{n-1}}$（$0\leq c\leq 10^9$）。这里 $c_i$ 指，若将 $\texttt{01}$ 串视为一个二进制数 $\overline{x_n \ldots x_1} $，那么 $c_i$ 即为值为 $i$ 的串带入 $f$ 得到的值 接下来 $r$ 行每行两个整数 $z, g$（$0\leq z\leq 2^n-1, 0\leq g\leq 10^9$），表示将 $c_z$ 修改为 $g$ ## 输出格式 共 $r+1$ 行。第 $1$ 行表示初始给出数据的答案，第 $r+1$ 行表示第 $r$ 次修改后的答案；每次的修改继承题目描述
Allen and Bessie are playing a simple number game. They both know a function $ f: \{0, 1\}^n \to \mathbb{R} $ , i. e. the function takes $ n $ binary arguments and returns a real value. At the start of the game, the variables $ x_1, x_2, \dots, x_n $ are all set to $ -1 $ . Each round, with equal probability, one of Allen or Bessie gets to make a move. A move consists of picking an $ i $ such that $ x_i = -1 $ and either setting $ x_i \to 0 $ or $ x_i \to 1 $ . After $ n $ rounds all variables are set, and the game value resolves to $ f(x_1, x_2, \dots, x_n) $ . Allen wants to maximize the game value, and Bessie wants to minimize it. Your goal is to help Allen and Bessie find the expected game value! They will play $ r+1 $ times though, so between each game, exactly one value of $ f $ changes. In other words, between rounds $ i $ and $ i+1 $ for $ 1 \le i \le r $ , $ f(z_1, \dots, z_n) \to g_i $ for some $ (z_1, \dots, z_n) \in \{0, 1\}^n $ . You are to find the expected game value in the beginning and after each change.输入输出格式
输入格式
The first line contains two integers $ n $ and $ r $ ( $ 1 \le n \le 18 $ , $ 0 \le r \le 2^{18} $ ). The next line contains $ 2^n $ integers $ c_0, c_1, \dots, c_{2^n-1} $ ( $ 0 \le c_i \le 10^9 $ ), denoting the initial values of $ f $ . More specifically, $ f(x_0, x_1, \dots, x_{n-1}) = c_x $ , if $ x = \overline{x_{n-1} \ldots x_0} $ in binary. Each of the next $ r $ lines contains two integers $ z $ and $ g $ ( $ 0 \le z \le 2^n - 1 $ , $ 0 \le g \le 10^9 $ ). If $ z = \overline{z_{n-1} \dots z_0} $ in binary, then this means to set $ f(z_0, \dots, z_{n-1}) \to g $ .
输出格式
Print $ r+1 $ lines, the $ i $ -th of which denotes the value of the game $ f $ during the $ i $ -th round. Your answer must have absolute or relative error within $ 10^{-6} $ . Formally, let your answer be $ a $ , and the jury's answer be $ b $ . Your answer is considered correct if $ \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