[Solution] Increasing Sequence Card Game solution kickstart

Increasing Sequence Card Game solution kickstart


Problem

You’re playing a card game as a single player.

There are NN cards. The ii-th card has integer ii written on it.

You first shuffle NN cards randomly and put them in a pile. Take the card at the top of the pile to your hand. Then repeat the following process until the pile becomes empty:

  1. Check the card on the top of the pile.
  2. If the number on the card is larger than the number on the last card you took, take the card.
  3. Otherwise, discard the card.
  4. Increasing Sequence Card Game solution kickstart

 

The score of the game is the number of cards in your hand at the end. With the given number of cards NN, what is the expected score of the game?

Input

The first line of the input contains the number of test cases, TTTT lines follow. Each line contains a single integer NN, the number of cards in the pile.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the expected score at the end of the game. Increasing Sequence Card Game solution kickstart

y will be considered correct if it is within an absolute or relative error of 10-6 of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept. Increasing Sequence Card Game solution kickstart

Limits

Time limit: 20 seconds.
Memory limit: 1 GB.
1T1001≤T≤100.

Test Set 1

1N101≤N≤10.

Test Set 2

1N1061≤N≤106.

Test Set 3

1N10181≤N≤1018.

Sample

Sample Input
content_copy
2
1
2
Sample Output
content_copy
Case #1: 1.0
Case #2: 1.5

Solution: Click here

 

Leave a Comment