P15111 Stellaris

You and a group of friends are slacking off together。

You open Stellaris and start a new game, turning on spectator mode。The game automatically generates $n$ civilizations, where the initial power rank of the $i$-th civilization is $i$。You decide to watch the game in the following way。 The game is divided into $k$ centuries。In the $i$-th century, there will be $a_i$ wars。Each war randomly selects one pair among the ${n \choose 2}$ pairs of different civilizations, and swaps their ranks。At the beginning of each century, everyone performs one civilization-picking step。Specifically, since you are the host, you may first decide whether to pick a civilization in this round。If yes, you choose any civilization that has not been chosen yet; otherwise, exactly one friend will choose the currently highest-ranked civilization among those that have not been chosen yet。After a civilization is chosen, it cannot be changed (that is, you can only choose at the beginning of a century)。 After discussing the rules, you become very interested in the optimal strategy for picking civilizations。So you plan to write a program to compute, for all $i$, if you pick a civilization at the beginning of the $i$-th century, what is the minimum possible expected final rank of the civilization you pick。Since you do not like taking modulo, you only need to output the answer rounded to five decimal places (printing more digits is also acceptable)。

The first line contains two integers $n, k$。 The second line contains $k$ integers, where the $i$-th integer represents $a_i$。

Output $k$ lines, one per line as described in the statement。

**This problem uses bundled testdata and Special Judge. Your answer is accepted as long as the difference from the standard answer does not exceed $10^{-5}$。** For $20\%$ of the testdata, $n, k, a_i \leq 3$。 For $60\%$ of the testdata, $n, k \leq 50$，$\sum a_i \leq 10000$。 For $100\%$ of the testdata, $n \leq 50$，$k \leq 50$，$0 \leq a_i \leq 10^7$，$k \leq n$。 Translated by ChatGPT 5