CODESPTF - Palindromes


 

Given a string, you keep swapping any two characters in the string randomly till the string becomes a palindrome. What is the expected number of swaps you will make?
Input:
The first line contains the number of test cases T. Each of the next T lines contains a string each.
Output:
Output T lines containing the answer for the corresponding test case. Print the answer rounded to exactly 4 decimal places.
Constraints:
T <= 10000
The length of the string will be at most 8 characters.
The string will consist of only lower-case letters 'a'-'z'.
There will always be at least one palindrome which can be formed with the letters of the given string.
Sample Input:
4
b
bb
abb
cbaabbb
Sample Output:
0.0000
0.0000
3.0000
59.3380
Explanation:
For the first two cases, the string is already a palindrome so no swaps are needed.
For the third case, there are 3 possible swaps. The string will become "bab","bba" or remain "abb" with 1/3rd probability each. It's easy to see that the expected number of swaps needed is 3.0000
For the last case, the answer is 59.337962..., which should be printed as 55.338

Given a string, you keep swapping any two characters in the string randomly till the string becomes a palindrome. What is the expected number of swaps you will make?

 

Input:

The first line contains the number of test cases T. Each of the next T lines contains a string each.

 

Output:

Output T lines containing the answer for the corresponding test case. Print the answer rounded to exactly 4 decimal places.

 

Constraints:

T <= 10000

The length of the string will be at most 8 characters.

The string will consist of only lower-case letters 'a'-'z'.

There will always be at least one palindrome which can be formed with the letters of the given string.

 

Sample Input:

4

b

bb

abb

cbaabbb

 

Sample Output:

0.0000

0.0000

3.0000

59.3380

 

Explanation:

For the first two cases, the string is already a palindrome so no swaps are needed.

For the third case, there are 3 possible swaps. The string will become "bab","bba" or remain "abb" with 1/3rd probability each. It's easy to see that the expected number of swaps needed is 3.0000

For the last case, the answer is 59.337962..., which should be printed as 55.3380


hide comments
#vaidy_MIT#: 2013-04-01 09:17:48

Which should be printed as 59.3380 ;) not 55.3380 :)


Added by:Varun Jalan
Date:2011-10-18
Time limit:0.547s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem used for CodeSprint - InterviewStreet Contest