Çoxölçülü gözləntilər#11527
Alisa və Bob sadə bir oyun oynayırlar. Onlar hər ikisi f:\{0,1\}^n \to \mathbb R funksiyasını bilirlər, yəni funksiya ikili arqument qəbul edir və həqiqi bir dəyər qaytarır. Oyunun əvvəlində bütün dəyişənlər x_1,x_2,...,x_n üçün olaraq təyin edilir. Hər raundda bərabər ehtimalla ya Alisa, ya da Bob bir hərəkət edə bilər. Hərəkət x_i=−1 olan bir seçməkdən və x_i \to 0 və ya x_i \to 1 təyin etməkdən ibarətdir.
raunddan sonra bütün dəyişənlər təyin edilir və oyunun nəticəsi f(x_1,x_2,...,x_n) olur. Alisa nəticəni maksimumlaşdırmaq, Bob isə minimumlaşdırmaq istəyir.
Sizin məqsədiniz Alisa və Bob-a oyunun nəticəsinin riyazi gözləntisini tapmağa kömək etməkdir! Onlar r+1 dəfə oynayacaqlar və oyunlar arasında yalnız bir dəyəri dəyişir. Başqa sözlə, 1 \le i \le r üçün və i+1 raundları arasında (z_1, ..., z_n) \in \{0,1\}^n dəsti üçün f(z_1, ..., z_n) dəyəri g_i ilə dəyişdiriləcək. Başlanğıcda və hər dəyişiklikdən sonra nəticənin riyazi gözləntisini tapın.
Birinci sətir iki tam ədəd və r~(1 \le n \le 18, 0 \le r \le 2^{18}) ehtiva edir.
Növbəti sətir 2^n tam ədəd c_0,c_1, ..., c_{2^n−1}~(0 \le c_i \le 10^9) ehtiva edir, bu da funksiyanın başlanğıc dəyərlərini göstərir. Formal olaraq, f(x_0,x_1,...,x_{n−1})=c_x, əgər x=\overline{x_{n−1}...x_0} ikili yazılışda olarsa.
Növbəti sətirin hər biri iki tam ədəd və g~(0 \le z \le 2^n−1, 0 \le g \le 10^9) ehtiva edir. Əgər z=\overline{z_{n−1}...z_0} ikili yazılışda olarsa, bu f(z_0,...,z_{n−1}) \to g dəyərinin dəyişdirilməsi deməkdir.
r+1 sətir çıxarın, burada -ci sətir -ci raundda oyununun dəyərini göstərir. Cavabınızın mütləq və ya nisbi xətası 10^{−6}-dan çox olmamalıdır.
Formal olaraq, cavabınız , münsiflərin cavabı isə olsun. Cavabınız doğru sayılacaq, əgər \frac{|a−b|}{max(1,|b|)} \le 10^{−6} olarsa.
İkinci test nümunəsini nəzərdən keçirək. Əgər Alisa birinci hərəkət edərsə, x_1 \to 1 təyin edəcək, beləliklə son dəyər olacaq. Əgər Bob birinci hərəkət edərsə, x_1 \to 0 təyin edəcək, beləliklə son dəyər olacaq. Beləliklə, cavab -dir.
Üçüncü giriş məlumatlarında oyunun nəticəsi Alisa və Bob-un oyunundan asılı olmayaraq həmişə olacaq.
Nümunə 1
Nümunə 2
Nümunə 3