主页 讨论版 问题 名次 状态 统计
欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~
问题 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

提示

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