1427 - Funny Funny Game
Time Limit : 1 Second
Memory Limit : 128 MB
Super Hanhan(SH) loves playing all kinds of little games very much. Today rocket323 recommends a new game to SH.
The game’s name is “Eating stones”, and it’s played like this: in a single round, the game system will randomly generate a sequence of N numbers(all of these N numbers are unique) representing the size of stones, and place them from left to right in a single line. Each time the player can choose one stone to eat, and then get a score of P points, which equal to number of remaining stones which are smaller than the chosen stone and to the left of the chosen stone.
SH wants to maximize the score he can get, however, he can’t figure out the best strategy to reach the goal. So he asks you(a talented programmer) for help.
Please help the poor SH find out the best strategy and tell him the expected scores he can get under this strategy.
There are multiple cases.
The first line is an integer T representing the number of test cases.
The following T lines each line representing a test case. For each case there is exactly one line containing a single number N, representing the number of stones in the game. (1 <= N <= 1000000)
For each test case, output a line containing the answer in the following format:
Case #K: X
K is the case number starting from 1, and X must be printed as a real number with two-digit precision, and the last decimal digit must be rounded.
- sample input
2 1 3
- sample output
Case #1: 0.00 Case #2: 1.50