Blindfold Nim

• 우선 스택이 1개만 있을때의 최적 전략이 무엇일지 생각해보자. 이길 확률을 가장 높이는 방법은 1개씩만 가져가는 방법이다. 최대한 자신이 이번턴에 죽지 않을 확률을 높이면서 상대방이 다음턴에 죽기를 기대하는 전략인데.. 대충 직관적인 느낌으로 최적 전략일것 같고, 실제로 작은 n값에 대해서 해보면 이게 최적으로 나온다. 일반화하는 것은 대충 수학적귀납법으로 증명할수 있을것 같긴 한데, 직관적으로 너무 확실해서 안해봐도 될것 같다.
• 조금 더 까다로운 것은 스택이 여러개 있을때의 최적 전략이다. 아까의 전략을 확장하면 이번에도 역시 가장 이번턴에 죽지 않을 확률을 높이는 전략을 취해야 한다. 즉 가장 동전이 많이 쌓인 스택에서 1개만 가져가는 것. 근데 이거는 직관적으로 이게 꼭 최적 전략일거라는 느낌은 좀 덜하다.. 그렇다고 진짜로 일일히 증명을 해보는 것은 귀찮고… 결국 proof by ac 를 하기로 했다..
• 그러면 가장 동전이 많이 쌓인 스택에서 1개만 가져가는 전략을 쓸때에 승리 확률은? 뭔가 O(스택갯수)에 풀수 있는 클로즈드 폼으로 나오면 좋겠지만, 잘 안나올것 같아서, 그냥 시뮬레이션 돌리면서 일일히 확률을 계산했다. 매턴 가장 동전이 많은 스택을 고르고, 거기에서 동전 하나씩을 빼게 되는데, 이것도 좀더 효율적으로 구현할수 있는 방법이 있겠지만 귀찮아서 그냥 우선순위큐에서 매번 n을 꺼내고 n-1을 다시 추가하는 식으로 처리했다.
• 다행히 proof by ac 성공.
• 시간복잡도는 모든 동전의 총 개수를 n, 스택의 갯수를 m이라고 할때, O(nlogm) 이다.

"""Solution code for "BOJ 8318. Blindfold Nim".

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

Tags: [game theory]
"""

import heapq


def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    answer = 0
    p = 1
    heap = [-a_i for a_i in a]
    heapq.heapify(heap)
    while heap:
        player_stack = -heapq.heappop(heap)
        p *= player_stack / (player_stack + 1)
        if player_stack > 1:
            heapq.heappush(heap, -(player_stack - 1))

        if not heap:
            answer += p
            break

        opponent_stack = -heapq.heappop(heap)
        answer += p / (opponent_stack + 1)
        p *= opponent_stack / (opponent_stack + 1)
        if opponent_stack > 1:
            heapq.heappush(heap, -(opponent_stack - 1))

    print(answer)


if __name__ == '__main__':
    main()