평균대

헛간에 새 축사를 마련할 돈을 모으기 위해, 소 베시는 지역 서커스에서 공연을 시작했다. 베시는 높이 설치된 평균대 위를 조심스럽게 왔다 갔다 걸으며 자신의 놀라운 균형 감각을 선보인다!

베시가 공연에서 버는 돈은 최종적으로 평균대에서 뛰어내리는 위치와 관련이 있다. 평균대에는 왼쪽부터 오른쪽으로 \(0, 1, \ldots, N+1\)의 위치 번호가 붙어 있다. 베시가 \(0\)이나 \(N+1\)에 도달하면 평균대의 한쪽 끝에서 떨어져 안타깝게도 아무 보수도 받지 못한다.

베시가 어떤 위치 \(k\)에 있을 때, 다음 중 하나를 할 수 있다.

1. 동전을 던진다. 뒷면이 나오면 위치 \(k-1\)로, 앞면이 나오면 위치 \(k + 1\)로 이동한다 (즉, 각 경우가 일어날 확률은 \(\frac{1}{2}\)이다).

2. 평균대에서 뛰어내리고 보수 \(f(k)\) \((0 \leq f(k) \leq 10^9)\)를 받는다.

베시는 자신의 이동이 무작위 동전 던지기에 좌우되기 때문에 특정한 보수 결과를 보장할 수 없다는 것을 알고 있다. 하지만 시작 위치에 따라, 최적의 결정 순서를 따를 때 ("최적"이란 기대 보수를 최대로 만드는 결정을 뜻한다) 기대 보수가 얼마가 될지 알고 싶어한다. 예를 들어 그녀의 전략이 확률 \(1/2\)로 \(10\), 확률 \(1/4\)로 \(8\), 확률 \(1/4\)로 \(0\)의 보수를 얻는다면, 기대 보수는 가중 평균인 \(10(1/2) + 8(1/4) + 0(1/4) = 7\)이 된다.

출제자: Franklyn Wang and Spencer Compton

출제자: Franklyn Wang and Spencer Compton

입력의 첫째 줄에 \(N\) (\(2 \leq N \leq 10^5\))이 주어진다. 나머지 \(N\)개의 줄에 \(f(1) \ldots f(N)\)이 주어진다.

\(N\)개의 줄을 출력한다. \(i\)번째 줄에는 베시가 위치 \(i\)에서 시작하여 최적으로 행동할 때의 기대 보수에 \(10^5\)를 곱한 값을 소수점 아래를 버림하여 정수로 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2018-2019 > December > Platinum