# Internet Problem Solving Contest

## Problem C – Card game

You are enjoying a lovely weekend afternoon in a new amusement park. The park also oﬀers a variety of activities that are about winning or losing a little money. One such activity has just caught your attention: a simple card game. As a person interested in puzzles and riddles, you almost instantly started to wonder: Should I pay for such a game? Am I expected to win or lose money while playing it?

This game is played with a standard deck of cards – there are four suits and in each suit cards worth 2 through 10, a Jack, a Queen, a King and an Ace. For the purpose of this problem, the Aces have value 1, Jacks 11, Queens 12, and Kings 13. In other words, each of the values 1 through 13 is present four times in the deck.

The simplest version of this game looks as follows: An employee of the amusement park shuﬄes the deck uniformly at random and gives you a card. Your winnings are equal to the value of the card.

Here is a more complicated version: As before, the dealer gives you a random card. You now have two options: either you take your winnings, or you return the card you have and ask for another one. The second one is again drawn uniformly at random, and you have to keep it.

The general version of this game has x turns, and you know x in advance. In each turn you can keep the card you have and end the game. In each turn except for the last one you can return the card and ask for another one.

In the easy data set the card you return is always returned back to the deck. Thus the new card you then get is always picked uniformly at random from a deck of 52 cards. In the hard data set the card you return is thrown away, so the more turns you take, the smaller the deck becomes.

Problem speciﬁcation

You are given the maximal number of turns x. Find the maximum expected amount of money you can win in a single game.

(In other words, ﬁnd the smallest y with the property: if playing a single game costed more than y, the amusement park would still proﬁt from the game, even if all players played it optimally.)

Input speciﬁcation

The ﬁrst line of the input ﬁle contains an integer t specifying the number of test cases. Each test case is preceded by a blank line. Each test case is given as a single line with a single integer x (between 1 and 52, inclusive).

Output speciﬁcation

For each test case, output a single line with one real number – the expected amount you will win if you follow an optimal strategy. Output at least 10 decimal places. Any answer with an absolute or relative error at most 109 will be accepted.

Example

input
1

1
output
7.000000000000

This is the correct answer both for the easy and the hard version, as for x = 1 they are the same: you have to keep the ﬁrst card you get. From the 52 cards, each card is picked with probability 152. There are 4 cards having each of the values 1 through 13. Hence the expected value of a card is i=113i (452) = 7.