Devus and their voting system
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Devus are creatures living in Devupur. There are total n Devus in Devupur. ith Devu live in ith house. Houses 1, 2, 3, , , n are placed in a single lane i.e. 1 is a neighbor of 2, 2 is a neighbor of 1 and 3 etc.
They decide their president by a very weird voting system. All the Devus contest in the presidential elections. Each person uniformly randomly votes any of the n person as his preference (he can vote himself too). Devus are really very envious creatures, so no Devu casts his vote to the person whom his neighbor has casted. Devus vote in the increasing order of their IDs.
Finally all the votes are counted and all the Devus having votes equal to highest voted Devu are selected as president.
Now you are interested in finding out expected number of presidents Devupur can select in their upcoming election. Please round the answer to 6 digits after decimal.
- First line of the input contains a single integer T denoting number of test cases.
- For each test case, there is a single line containing a single integer n.
OutputFor each test case, print a single real number corresponding to the answer of the problem.
Constraints and SubtasksSubtask 1 (15 points)
- 1 ≤ T, n ≤ 7
- 1 ≤ T, n ≤ 18
- 1 ≤ T, n ≤ 36
Input: 2 1 2 Output: 1.000000 2.000000
Example 1: 1st Devu votes himself and get elected for president. So expected number of presidents are 1.
- Both the Devus cast their vote to themselves. So total number of presidents selected are 2.
- Devu 1 votes to Devu 2 and Devu 2 votes to Devu 1. In this way, again total total number of presidents selected are 2.
- So expected number of presidents selected are (2 + 2) / 2 = 2.
|Tags||admin2, april15, dynamic-programming, medium-hard, partitioning|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.