Viga de equilibrio#10402
Para ahorrar dinero para un nuevo establo en su granero, la vaca Bessie ha comenzado a actuar en el circo local, demostrando su notable sentido del equilibrio mientras camina cuidadosamente de un lado a otro sobre una viga de equilibrio elevada.
La cantidad de dinero que Bessie gana por su actuación depende del lugar donde finalmente salte de la viga. Las posiciones en la viga están etiquetadas como , , , n + 1 de izquierda a derecha. Si Bessie llega a la posición o n + 1, se cae de uno de los extremos de la viga y, lamentablemente, no recibe ningún pago.
Cuando Bessie está en la posición , puede hacer una de las siguientes cosas:
Lanzar una moneda. Si sale cruz, se mueve a la posición k - 1; si sale cara, se mueve a la posición k + 1 (es decir, cada resultado ocurre con probabilidad ).
Saltar de la viga y recibir un pago de f(k)~(0 \le f(k) \le 10^9).
Bessie se da cuenta de que no puede garantizar ningún pago en particular, ya que su movimiento está gobernado por lanzamientos de moneda aleatorios. Sin embargo, para cada posición inicial, quiere determinar su pago esperado si toma una secuencia óptima de decisiones (es decir, decisiones que conduzcan al mayor pago esperado posible). Por ejemplo, si su estrategia le proporciona un pago de con probabilidad , con probabilidad , y con probabilidad , entonces su pago esperado es el promedio ponderado 10 \cdot (1/2) + 8 \cdot (1/4) + 0 \cdot (1/4) = 7.
La primera línea contiene un entero n~(2 \le n \le 10^5). Las siguientes líneas contienen los valores , , , uno por línea.
Imprime líneas. La línea -ésima debe contener el pago esperado de Bessie cuando comienza en la posición y juega de manera óptima, multiplicado por 10^5 y redondeado hacia abajo.
Ejemplo 1