A11783. Game
编程题
普及/提高-
知识点
题目描述
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.
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$ .
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}$ .
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
说明/提示
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.
In the third test case, the game value will always be $1$ regardless of Allen and Bessie's play.