Costly Strings

5

3 votes
Cayley Hamilton, Exception handling, Recursion, Hard, Error analysis, Mathematics, Probability and Statistics
Problem

Let us define the cost of a string S as the length of the longest substring of S which has all the characters same. For example, the cost of string abaaaba is 3, and the cost of string abcd is 1.

You found a new language L containing c distinct characters. Language L contains only all strings of length n which can be formed from these c characters. Now, you choose a string at random from these cn strings. Find the expected value of the cost of this string.

You will be given T test cases, each containing c and n. Your answer is considered correct if the absolute OR relative error between the actual answer and your answer is <106

Input

  • The first line contains T, the number of test cases.
  • ith of the next T lines contain two integers, c and n, the number of distinct characters, and the length of strings in L respectively.

Output
Print T lines . The ith line should contain the answer to the ith test case

Constraints

  • 1T50

  • 1c,n109

Sample Input
2
2 3
3 2
Sample Output
2.0000000000
1.3333333333
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

In the first test case, c=2, n=3. Lets say the c distinct characters are 0,1. Then the strings are:

  • 000 having cost 3
  • 001 having cost 2
  • 010 having cost 1
  • 011 having cost 2
  • 100 having cost 2
  • 101 having cost 1
  • 110 having cost 2
  • 111 having cost 3

The expectation value of cost is 3+2+1+2+2+1+2+38=2

In the second test case, the probability that both characters of string are same is 13. So, the expectation value is 23×1+13×2=43

Contributers:
Editor Image

?