슬롯 게임

Alice와 Bob은 다음 게임을 한다. 처음에 두 사람은 각각 N장의 카드를 받는데, 각 카드에는 구간 [1, 1018]에서 균등하고 독립적으로 무작위로 선택된 정수가 적혀 있다. 또한 1번부터 N번까지 번호가 붙은 N개의 슬롯이 있다.

Alice가 먼저 자신의 카드를 슬롯에 놓는데, 각 슬롯에 정확히 한 장씩 놓는다. 그녀는 N! 가지 배치 중 원하는 것을 고를 수 있다. 그다음 Bob은 각 슬롯에 Alice가 놓은 숫자를 보고 자신의 카드로 같은 일을 한다. 그러면 게임이 끝나고, 각 슬롯 i에 대해 더 큰 숫자를 놓은 사람이 i점을 얻는다 (i = 1, 2, . . . , N). 만약 두 사람이 놓은 숫자가 같으면 그 슬롯의 점수를 나눠 가지므로, 각자 i/2점을 얻는다.

게임의 예로, N = 3이고 Alice가 10, 20, 40이 적힌 카드를, Bob이 10, 30, 50이 적힌 카드를 받았다고 하자. Alice는 슬롯 1, 2, 3에 각각 40, 20, 10을 놓을 수 있다. 그녀의 수를 본 Bob은 슬롯 1, 2, 3에 각각 30, 50, 10을 놓을 수 있다. 이 경우 Alice는 슬롯 1에서 1점, 슬롯 2에서 0점, 슬롯 3에서 3/2 = 1.5점을 얻는다. 그녀의 총점은 2.5점이다.

위 예는 게임의 규칙을 설명하기 위한 것이다. 두 사람 모두 최적으로 플레이하므로 Alice와 Bob이 설명한 대로 카드를 놓지 않을 수도 있다. 이것이 무슨 뜻인지 궁금할 수 있다.

Bob은 자신의 차례에 Alice의 카드와 선택에 대한 모든 정보를 알고 있으며, 물론 자신의 카드도 안다. 그는 자신의 총점을 최대화하도록 플레이한다.

반면 Alice는 자신의 차례에 Bob의 카드를 모른다. 그녀는 Bob의 전략을 알고 있고, 그의 카드가 균등하게 무작위로 선택되었다는 것도 안다. 따라서 그녀는 자신의 총점의 기댓값을 최대화하도록 플레이한다.

N이 주어질 때, 두 사람이 위에서 설명한 대로 최적으로 플레이할 때 게임이 끝난 뒤 Alice의 총점의 기댓값을 계산해야 한다.

입력은 게임의 슬롯 수 N (1 ≤ N ≤ 100)을 포함하는 한 줄로 이루어진다.

두 사람이 위에서 설명한 대로 최적으로 플레이할 때 게임이 끝난 뒤 Alice의 총점의 기댓값을 나타내는 수를 한 줄에 출력한다. 결과는 소수점 아래 정확히 여섯 자리의 유리수로 출력해야 하며, 필요하면 반올림한다.