Багатовимірні очікування#11527

Багатовимірні очікування

3 секунди

256 мегабайтів

Складна

Аліса та Боб грають у просту гру з числами. Вони обидва знають функцію $f : {0, 1}^{n} \to R$ f:\{0,1\}^n \to \mathbb R, яка приймає $n$ двійкових аргументів і повертає дійсне значення. На початку гри всім змінним $x_{1}, x_{2}, ..., x_{n}$ x_1,x_2,...,x_n присвоюється значення $- 1$ . У кожному раунді з рівною ймовірністю або Аліса, або Боб можуть зробити хід. Хід полягає у виборі $i$ такого, що $x_{i} = - 1$ x_i=−1, і присвоєнні $x_{i} \to 0$ x_i \to 0 або $x_{i} \to 1$ x_i \to 1.

Після $n$ раундів всі змінні встановлені, і результатом гри стає $f (x_{1}, x_{2}, ..., x_{n})$ f(x_1,x_2,...,x_n). Аліса хоче максимізувати результат, а Боб хоче його мінімізувати.

Ваша мета — допомогти Алісі та Бобу знайти математичне сподівання результату гри! Вони будуть грати $r + 1$ r+1 разів, і між іграми змінюється рівно одне значення $f$ . Іншими словами, між раундами $i$ та $i + 1$ i+1 для $1 \leq i \leq r$ 1 \le i \le r, буде змінено значення $f (z_{1}, ..., z_{n}) \to g_{i}$ f(z_1, ..., z_n) \to g_i для деякого набору $(z_{1}, ..., z_{n}) \in {0, 1}^{n}$ (z_1, ..., z_n) \in \{0,1\}^n. Знайдіть математичне сподівання результату на початку, а також після кожної зміни.

Вхідні дані

Перший рядок містить два цілих числа $n$ і $r$ $(1 \leq n \leq 18, 0 \leq r \leq 2^{18})$ (1 \le n \le 18, 0 \le r \le 2^{18}).

Наступний рядок містить $2^{n}$ 2^n цілих чисел $c_{0}, c_{1}, ..., c_{2^{n} - 1}$ c_0,c_1, ..., c_{2^n−1} $(0 \leq c_{i} \leq 1 0^{9})$ (0 \le c_i \le 10^9), що позначають початкові значення функції $f$ . Формально, $f (x_{0}, x_{1}, ..., x_{n - 1}) = c_{x}$ f(x_0,x_1,...,x_{n−1})=c_x, якщо $x = x_{n - 1} ... x_{0}$ x=\overline{x_{n−1}...x_0} у двійковому записі.

Кожен з наступних $r$ рядків містить два цілих числа $z$ і $g$ $(0 \leq z \leq 2^{n} - 1, 0 \leq g \leq 1 0^{9})$ (0 \le z \le 2^n−1, 0 \le g \le 10^9). Якщо $z = z_{n - 1} ... z_{0}$ z=\overline{z_{n−1}...z_0} у двійковому записі, то це означає зміну значення $f (z_{0}, ..., z_{n - 1}) \to g$ f(z_0,...,z_{n−1}) \to g.

Вихідні дані

Виведіть $r + 1$ r+1 рядків, $i$ -й з яких позначає вартість гри $f$ у $i$ -му раунді. Ваша відповідь повинна мати абсолютну або відносну помилку не більше $1 0^{- 6}$ 10^{−6}.

Формально нехай ваша відповідь буде $a$ , а відповідь журі — $b$ . Ваша відповідь буде вважатися правильною, якщо $\frac{∣ a - b ∣}{ma x ( 1 , ∣ b ∣ )} \leq 1 0^{- 6}$ \frac{|a−b|}{max(1,|b|)} \le 10^{−6}.

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

Розглянемо другий тестовий випадок. Якщо Аліса піде першою, вона встановить $x_{1} \to 1$ x_1 \to 1, так що остаточне значення буде $3$ . Якщо Боб ходить першим, то він встановить $x_{1} \to 0$ x_1 \to 0, так що остаточне значення буде дорівнювати $2$ . Таким чином, відповідь дорівнює $2.5$ .

У третьому наборі вхідних даних результат гри завжди буде дорівнювати $1$ , незалежно від гри Аліси і Боба.