In order to save money for a new stall in her barn, bessie the cow has started performing in the local circus, demonstrating her
remarkable sense of balance as she carefully walks back and forth on an elevated balance beam!
the amount of money bessie earns in her performance is related to where she manages to ultimately jump off the beam. the
beam has positions labeled 0, 1, + 1 from left to right. if bessie ever reaches 0 or n + 1 she falls off one of the ends of the
beam and sadly gets no payment.
if bessie is at a given position k, she can do either of the following:
1. flip a coin. if she sees tails, she goes to position k-1, and if she sees heads, she goes to position k + 1 (.e.
either occurrence).
probability of
2. jump off the beam and receive payment of f(k) (0 bessie realizes that she may not be able to guarantee any particular payment outcome, since her movement is governed by
random coin flips. however, based on the location where she starts, she wants to determine what her expected payment will be
if she makes an optimal sequence of decisions ("optimal" meaning that the decisions lead to the highest possible expected
payment). for example, if her strategy earns her payment of 10 with probability 1/2, 8 with probability 1/4, or 0 with probability
1/4, then her expected payment will be the weighted average 10(1/2) + 8(1/4) + 0(1/4) = 7.
input format (file balance. in):
the first line of input contains n (2 sn 310). each of the remaining n lines contain f( f(n).
output format (file balance. out):
output n lines. on linei, print out 10 times the expected value of payment if bessie starts at position i and plays optimally,
rounded down to the nearest integer.