408550: GYM103185 G Game of Slots

Alice and Bob are playing the following game. Initially, each of them receives $$$N$$$ cards, each card with an integer randomly and uniformly chosen from the interval $$$[1, 10^{18}]$$$ written on it. There are also $$$N$$$ slots, numbered from $$$1$$$ to $$$N$$$.

Alice starts by placing her cards on the slots, in such a way that exactly one card is placed on each slot. She may choose any of the $$$N!$$$ options of placement she wants. After that, Bob looks at the numbers placed by Alice on each slot and does the same with his cards. The game then ends, and for each slot $$$i$$$ the person who placed the largest number on it earns $$$i$$$ points ($$${i}={1}, {2}, \ldots, {N}$$$). If both of the placed numbers happen to be equal, the players share the points for this slot, that is, each player gets $$$i/2$$$ points.

As an example of the game, suppose $$$N = 3$$$, Alice is given cards with numbers $$$10$$$, $$$20$$$ and $$$40$$$, and Bob is given cards with numbers $$$10$$$, $$$30$$$ and $$$50$$$. Alice may choose to place numbers $$$40$$$, $$$20$$$ and $$$10$$$ on slots $$$1$$$, $$$2$$$ and $$$3$$$ respectively. After seeing her moves Bob may choose to place numbers $$$30$$$, $$$50$$$ and $$$10$$$ on slots $$$1$$$, $$$2$$$ and $$$3$$$ respectively. In this case, Alice earns $$$1$$$ point for slot $$$1$$$, $$$0$$$ points for slot $$$2$$$, and $$$3/2=1.5$$$ points for slot $$$3$$$. Her total score is $$$2.5$$$ points.

The purpose of the above example is to illustrate the rules of the game. Alice and Bob may not place their cards as described, because both of them play optimally. You may wonder what does it mean.

In his turn, Bob has full information on Alice's cards and decisions, and of course, he knows his cards. He plays in such a way to maximize his total score.

On the other hand, Alice does not know Bob's cards when it's her turn. She knows Bob's strategy, and that his cards were randomly and uniformly chosen. Thus, she plays to maximize the expected value of her total score.

Given $$$N$$$, you must calculate the expected value of Alice's total score at the end of the game, if the players play optimally as described.

The input consists of a single line that contains an integer $$$N$$$ ($$$1 \le N \le 100$$$), the number of slots in the game.

Output a single line with a number indicating the expected value of Alice's total score at the end of the game, if the players play optimally as described. The result must be output as a rational number with exactly six digits after the decimal point, rounded if necessary.

1

0.500000

2

1.333333

99

589.631287