{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"challenge_problem_statement\"\u003e\u003cdiv class\u003d\"msB challenge_problem_statement_body\"\u003e\u003cdiv class\u003d\"hackdown-content\"\u003e\u003cstyle id\u003d\"MathJax_SVG_styles\"\u003e.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%}\n.MathJax_SVG .MJX-monospace {font-family: monospace}\n.MathJax_SVG .MJX-sans-serif {font-family: sans-serif}\n.MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0}\n.MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none}\n.mjx-svg-href {fill: blue; stroke: blue}\n.MathJax_SVG_LineBox {display: table!important}\n.MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}\n\u003c/style\u003e\u003csvg style\u003d\"display: none;\"\u003e\u003cdefs id\u003d\"MathJax_SVG_glyphs\"\u003e\u003c/defs\u003e\u003c/svg\u003e\u003cp\u003eGiven a string, you keep swapping any two characters in the string randomly till the string becomes a palindrome. What is the \u003ca href\u003d\"http://en.wikipedia.org/wiki/Expected_value\"\u003eexpected number\u003c/a\u003e of swaps you will make?\u0026nbsp;There will always be at least one palindrome which can be formed with the letters of the given string.\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003eInput:\u003c/strong\u003e \u003cbr\u003e\nThe first line contains the number of test cases T. Each of the next T lines contains a string each.\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003eOutput:\u003c/strong\u003e \u003cbr\u003e\nOutput T lines containing the answer for the corresponding test case. Print the answer correct to 4 decimal places.\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003eConstraints:\u003c/strong\u003e \u003cbr\u003e\nT \u0026lt;\u003d 10000 \u003cbr\u003e\nThe length of the string will be at most 8 characters. \u003cbr\u003e\nThe string will consist of only lower-case letters \u0027a\u0027-\u0027z\u0027.\u003c/p\u003e\n\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 \nb \nbb \nabb \ncbaabbb\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0.0000 \n0.0000 \n3.0000 \n59.3380\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\n\n\n\n\n\n\n\n\u003cp\u003e\u003cstrong\u003eExplanation:\u003c/strong\u003e\u003c/p\u003e\n\n\u003cp\u003eFor the first two cases, the string is already a palindrome so no swaps are needed.\u003c/p\u003e\n\n\u003cp\u003eFor the third case, there are 3 possible swaps. The string will become \"bab\",\"bba\" or remain \"abb\" with 1/3rd probability each. It\u0027s easy to see that the expected number of swaps needed is 3.0000\u003c/p\u003e\n\n\u003cp\u003eFor the last case, the answer is 59.337962..., which should be printed as 59.3380\u003c/p\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e"}}]}