복권 + 은행

• 처음에 별생각 없이 O(n^2) dp로 풀었었는데, 풀고 나서 내코드가 다른 코드들보다 훨씬 느리다는 것을 파악하고서 단순히 O(n)으로 푸는 방법이 있다는 것을 알게되었다.
• DP풀이부터 설명하자
• 처음에 정보가 과다하게 주어지는 편인데, 실제로 당첨 확률을 계산하는 데에 있어서 다른 사람들의 각각의 잔고 분포는 중요치가 않다. 따라서, 모든 사람의 잔고의 합과, 내 잔고만 관리하면 된다.
• 내 잔고의 상태는, 당첨된 횟수만 알면 {처음 잔고} + J*{당첨횟수} 로 구할수 있으므로, 금액 대신 그냥 당첨된 횟수로 표현하면 된다. 각 날짜별로, 그때까지 k번 당첨되었을 확률을 dp로 관리하면 된다. dp[i][j]에 i일까지 j번 당첨되었을 확률을 저장하면 점화식은 아래처럼 된다
  • dp[n][m] = dp[n-1][m-1] * {이번에 당첨될 확률} + dp[n][m-1] * {이번에 당첨안될 확률}
  • n-1일 까지 m번 당첨되었을때, n일째에 당첨될 확률 = {첫날잔고 + m*J} / {첫날의 전체 잔고합 + (n-1)*J}
• 테이블 크기는 O(n^2)이고, 테이블 한칸을 채우는데는 O(1)이 걸리므로 총 O(n^2)에 풀수있다. n이 최대 1000이므로 이렇게 구현해도 빠르게 (내경우 168ms) 에 풀린다.
• 하지만 이것보다 훨씬 간단한 풀이가 있다. n일째의 잔고를, 가능한 금액별로 확률을 각각 관리하는 것이 아니라, 그냥 잔고의 기댓값 하나만을 관리하는 것이다. 이것만으로도 당첨될 확률을 구할수 있고, 다음날의 잔고의 기댓값을 갱신하는것도 가능하다. 간단하게 설명하면
  • {당첨 확률}=sum_x({잔고가 x일 확률} * {잔고가 x일때 당첨확률}) 인데, 여기서 {잔고가 x일때 당첨확률} = x/{전체잔고} 이므로
  • {당첨 확률}=sum_x({잔고가 x일 확률} * x/{전체잔고})= sum_x({잔고가 x일 확률} * x)/{전체잔고} = {기대잔고}/{전체잔고} 가 된다.
• 매일 기대잔고와 전체잔고만 O(1)에 갱신해주면 되므로, 총 시간복잡도는 O(n)이 된다.

"""Solution code for "BOJ 13258. 복권 + 은행".

- Problem link: https://www.acmicpc.net/problem/13258
- Solution link: http://www.teferi.net/ps/problems/boj/13258

Tags: [dp]
"""


def main():
    N = int(input())  # pylint: disable=unused-variable
    balances = [int(x) for x in input().split()]
    J = int(input())
    C = int(input())

    init_balance = balances[0]
    tot_balance = sum(balances)
    dp_cur = [1.0, 0.0]  # dp_cur[x] = probability of winning x times so far
    for j in range(1, C + 1):
        dp_prev, dp_cur = dp_cur, [0.0] * (j + 2)
        dp_cur[0] = dp_prev[0] * (1 - (init_balance / tot_balance))
        for i in range(1, j + 1):
            dp_cur[i] = (
                dp_prev[i - 1] * (init_balance + (i - 1) * J)
                + dp_prev[i] * (tot_balance - (init_balance + i * J))
            ) / tot_balance
        tot_balance += J

    answer = init_balance + J * sum(x * prob for x, prob in enumerate(dp_cur))
    print(answer)


if __name__ == '__main__':
    main()

"""Solution code for "BOJ 13258. 복권 + 은행".

- Problem link: https://www.acmicpc.net/problem/13258
- Solution link: http://www.teferi.net/ps/problems/boj/13258

Tags: [math]
"""


def main():
    N = int(input())  # pylint: disable=unused-variable
    balances = [int(x) for x in input().split()]
    J = int(input())
    C = int(input())

    expected_my_balance = balances[0]
    tot_balance = sum(balances)
    for _ in range(C):
        expected_my_balance += (expected_my_balance / tot_balance) * J
        tot_balance += J

    print(expected_my_balance)


if __name__ == '__main__':
    main()