English · Original
Chinese · Translation
Formal · Original
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.
## Input
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$.
## Output
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}$.
[samples]
## Note
Consider the second test case. If Allen goes first, he will set $x_1 \to 1$, so the final value will be $3$. If Bessie goes first, then she will set $x_1 \to 0$ so the final value will be $2$. Thus the answer is $2.5$.
In the third test case, the game value will always be $1$ regardless of Allen and Bessie's play.
Allen 和 Bessie 正在玩一个简单的数字游戏。他们都知道一个函数 $f : {0, 1}^n \to \mathbb{R}$，即该函数接受 $n$ 个二进制输入并返回一个实数值。游戏开始时，变量 $x_1, x_2, \dots, x_n$ 均被设为 $-1$。每一轮，Allen 或 Bessie 以相等概率获得行动权。一次行动是指选择一个满足 $x_i = -1$ 的 $i$，并将 $x_i$ 设为 $0$ 或 $1$。
经过 $n$ 轮后，所有变量均被设定，游戏的值变为 $f (x_1, x_2, \dots, x_n)$。Allen 希望最大化游戏值，而 Bessie 希望最小化它。
你的目标是帮助 Allen 和 Bessie 计算期望的游戏值！不过他们会进行 $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$ 的初始值。更具体地，若 $x = \overline{x_{n-1} \dots x_0}$（二进制表示），则 $f (x_0, x_1, \dots, x_{n-1}) = c_x$。
接下来的 $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}$ 时，你的答案被视为正确。
考虑第二个测试用例：若 Allen 先行动，他会将 $x_1$ 设为 $1$，因此最终值为 $3$；若 Bessie 先行动，她会将 $x_1$ 设为 $0$，因此最终值为 $2$。因此答案为 $2.5$。
在第三个测试用例中，无论 Allen 和 Bessie 如何行动，游戏值始终为 $1$。
## Input
第一行包含两个整数 $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$ 的初始值。更具体地，若 $x = \overline{x_{n-1} \dots x_0}$（二进制表示），则 $f (x_0, x_1, \dots, x_{n-1}) = c_x$。接下来的 $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$。
## Output
请输出 $r + 1$ 行，第 $i$ 行表示第 $i$ 轮游戏的 $f$ 值。你的答案绝对误差或相对误差不得超过 $10^{-6}$。形式化地，设你的答案为 $a$，标准答案为 $b$，当且仅当 $\frac{| a - b |}{\max (1, | b |)} \le 10^{-6}$ 时，你的答案被视为正确。
[samples]
## Note
考虑第二个测试用例：若 Allen 先行动，他会将 $x_1$ 设为 $1$，因此最终值为 $3$；若 Bessie 先行动，她会将 $x_1$ 设为 $0$，因此最终值为 $2$。因此答案为 $2.5$。在第三个测试用例中，无论 Allen 和 Bessie 如何行动，游戏值始终为 $1$。
**Definitions**
Let $ n \in \mathbb{Z}^+ $, $ r \in \mathbb{Z}_{\geq 0} $.
Let $ f: \{0,1\}^n \to \mathbb{R} $ be a function represented by a vector $ \mathbf{c} = (c_0, c_1, \dots, c_{2^n - 1}) $, where $ c_x = f(x_0, x_1, \dots, x_{n-1}) $ for $ x = \sum_{i=0}^{n-1} x_i 2^i $ (little-endian binary representation).
Let $ \mathbf{x} = (x_1, x_2, \dots, x_n) \in \{-1, 0, 1\}^n $ denote the state vector, initially $ \mathbf{x} = (-1, -1, \dots, -1) $.
Each round, a player (Allen or Bessie, chosen uniformly at random) selects an index $ i $ with $ x_i = -1 $ and sets $ x_i \in \{0,1\} $.
Allen aims to **maximize** $ f(\mathbf{x}) $; Bessie aims to **minimize** it.
Let $ V(\mathbf{x}) $ denote the expected game value from state $ \mathbf{x} $ under optimal play.
**Constraints**
1. $ 1 \leq n \leq 18 $
2. $ 0 \leq r \leq 2^{18} $
3. $ 0 \leq c_i \leq 10^9 $ for all $ i \in \{0, 1, \dots, 2^n - 1\} $
4. Each update: $ z \in \{0, 1, \dots, 2^n - 1\} $, $ g \in [0, 10^9] $, set $ c_z \leftarrow g $
**Objective**
Compute $ V(\mathbf{-1}) $, the expected value of the game starting from $ \mathbf{x} = (-1, \dots, -1) $, after each of $ r+1 $ updates to $ f $ (including the initial state).
The recurrence for $ V(\mathbf{x}) $ is:
- If $ \mathbf{x} \in \{0,1\}^n $, then $ V(\mathbf{x}) = f(\mathbf{x}) $.
- Otherwise, let $ S = \{ i \mid x_i = -1 \} $, $ m = |S| $.
Then:
$$
V(\mathbf{x}) = \frac{1}{2m} \sum_{i \in S} \left( \max_{b \in \{0,1\}} V(\mathbf{x}[i \leftarrow b]) + \min_{b \in \{0,1\}} V(\mathbf{x}[i \leftarrow b]) \right)
$$
(Because with probability $ \frac{1}{2} $, Allen moves and chooses $ \arg\max $, and with probability $ \frac{1}{2} $, Bessie moves and chooses $ \arg\min $, and each $ i \in S $ is chosen uniformly.)
Equivalently, for each unset variable $ i $, the contribution is the average of the max and min over its two possible assignments:
$$
V(\mathbf{x}) = \frac{1}{|S|} \sum_{i \in S} \frac{ V(\mathbf{x}[i \leftarrow 0]) + V(\mathbf{x}[i \leftarrow 1]) }{2}
$$
Thus, the value at any state depends only on the values of its immediate extensions, and the full function $ f $ is updated dynamically.
We are to output $ V(\mathbf{-1}) $ after each update to $ f $, for $ r+1 $ total outputs.
API Response (JSON)
{
"problem": {
"name": "F. Game",
"description": {
"content": "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 g",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF996F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 g...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Allen 和 Bessie 正在玩一个简单的数字游戏。他们都知道一个函数 $f : {0, 1}^n \\to \\mathbb{R}$，即该函数接受 $n$ 个二进制输入并返回一个实数值。游戏开始时，变量 $x_1, x_2, \\dots, x_n$ 均被设为 $-1$。每一轮，Allen 或 Bessie 以相等概率获得行动权。一次行动是指选择一个满足 $x_i = -1$ 的 $i$，并将 $...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $, $ r \\in \\mathbb{Z}_{\\geq 0} $. \nLet $ f: \\{0,1\\}^n \\to \\mathbb{R} $ be a function represented by a vector $ \\mathbf{c} = (c_0, c_1, \\dots, c_{2^n - 1}) $...",
"is_translate": false,
"language": "Formal"
}
]
}