OpenKattis
AAPS19 Session 07

Start

2019-05-20 03:10 AKDT

AAPS19 Session 07

End

2019-05-20 06:30 AKDT
The end is near!
Session is over.
Not yet started.
Session is starting in -617 days 14:44:29

3:20:00

0:00:00

Problem DMemory Game

Photo by Matthew Roth.

The game of Memory is played with $N$ pairs of cards where each pair has the same picture, i.e. there are $N$ different pictures, and each of them appear on exactly two cards.

The cards are shuffled and placed face down on a large table. On each turn you flip two cards of your choice face up. If they match you remove them from the game, and if they don’t match, you turn them face down. The goal of the game is to remove all cards from the game.

• If you know of two face-down cards which have the same picture, choose both of them.

• Otherwise,

• Turn a random card that you have not looked at before face up.

• If it matches a card you have seen, turn the matching card face up (you have excellent memory).

• If the first card did not match a card you had seen before, turn another random unknown card face up.

Given this strategy, what is the expected number of turns you have to play in order to finish the game?

Input

Input is a single integer $N$ indicating the number of pairs of cards.

Output

Output the expected number of turns needed to finish the game. This number must have an absolute or relative error of at most $10^{-6}$.

Limits

• $1 \leq N \leq 1\, 000$

Sample Input 1 Sample Output 1
1

1.000000000

Sample Input 2 Sample Output 2
2

2.666666666667