主页 讨论版 问题 名次 状态 统计
12月将举办首届西电ACM新生赛,敬请期待~~~~
问题 I: Filth in Gensoukyou

问题 I: Filth in Gensoukyou

时间限制: 1 Sec  内存限制: 128 MB  Special Judge
提交: 35  解决: 22
[提交][状态][讨论版]

题目描述

Sagume finds that there is too much filth in Gensoukyou that she can't endure any more. She decides to clean up the Gensoukyou. There are N places in Gensoukyou which form a straight line, numbered from 1 to N. Places with the adjacent number can reach each other. To clean up all places, Sagume will follow the following procedure:

1. She randomly choose a place within the current connected component and clean it out. It will take her S seconds, in which S represents the current connected component's size.
2. She cut off the chosen place, then there will appear at most 2 new connected components.
3. She subsequently go to clean up the new components.

As a grand sage, Sagume is tight for time. She wants to know the expected time she will cost in order to schedule her time.

输入

The first line contains an integer T, the number of test cases.
Each test case contains an integer N, the number of places in Gensoukyou.
It is guaranteed that 1<=T<=1e4 and 1<=N<=1e6.

输出

For each test case, output one real number within a single line, which is the expected time(seconds) Sagume will cost. Your answer will be considered correct if its absolute error does not exceed 1e-4.

样例输入

2
3
4

样例输出

5.6667
8.8333

提示

[提交][状态][讨论版]