410047: GYM103931 I It Takes Two of Two

Nice cooperation helps. Bad cooperation sucks.

A sittable chair and a sleepy Sayu.

As the leader of Mihomo, a company producing sittable chairs, Koji is encouraging cooperation to enlarge the scale of production pipeline. In order to guarantee the quality of cooperation, here are three requirements that the cooperation relations must satisfy:

• Each cooperation relation involves $$$2$$$ different employees.
• No two cooperation relations involve the same pair of employees.
• Each employee must participate in no more than $$$2$$$ different cooperation relations.

There are $$$n$$$ employees in the company, including Koji himself. Koji considered it very important to make fair cooperation. The dice never lie, so he decided to roll some dice to decide the fair division. The procedure of the dice rolling is as follows:

• Initially, the set $$$R$$$ of cooperation relations is empty set ($$$\varnothing$$$), and then starts to enter a loop.
• In each iteration, two integers $$$u, v$$$ are independently chosen from $$$1, 2 \dots, n$$$ uniformly at random. If $$$R \cup (u, v)$$$ meets above requirements, add $$$(u, v)$$$ to $$$R$$$, otherwise leave $$$R$$$ unchanged.
• Before the beginning of each iteration, if no more cooperation could be added to $$$R$$$, the program terminates immediately.

Koji wrote a program of the above procedure in just $$$114$$$ seconds, but he finds that it had taken $$$514$$$ seconds until the program finished its execution. Since Koji is not good at counting numbers above nine, he wants you to help him calculate the expected number of iterations of the above procedure in order to decide if there is a potential bug in the program.

Input contains a single integer $$$n (1 \leq n \leq 200)$$$, the number of employees in Mihomo.

Print a single real number in decimal, denoting your answer.

Your answer will be considered correct, if the absolute error or relative error to the reference answer is less than $$$10^{-6}$$$.

To print a fixed decimal number for some digits after the decimal point, say, $$$9$$$ digits, you can use

• printf("%.9lf\n", ans) or printf("%.9Lf\n", ans) in C-style output;
• cout << fixed << setprecision(9) << ans << endl in C++;
• print("%.9f" % ans) in Python;
• see documentation for other languages.

1

0.000000000

2

2.000000000

3

8.250000000

For the first sample case, Koji can cooperate with nobody, so the program terminates immediately.

For the second sample case, either $$$\{(1, 2)\}$$$ or $$$\{(2, 1)\}$$$ will be the final $$$R$$$, and with probability $$$1/2$$$ invalid cooperation relations $$$(1, 1), (2, 2)$$$ can be obtained. Therefore, the expected number of iterations is $$$$$$1 \times (1/2) + 2 \times (1/4) + 3 \times (1/8) + \cdots = 2.$$$$$$