{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e你能想象一只猴子写电脑程序吗?毫无疑问,猴子在动物中算是聪明的。但是它们有限的智力无法与我们人类相提并论。然而,有一个关于猴子的定理,它声称只要给予足够的时间,猴子就能写出任何东西。\u003cbr\u003e这个定理被称为“无限猴子定理”。它声称,一只猴子在打字机键盘上随机按键无限长的时间后,几乎肯定会打出任何给定的文本,当然也包括你即将要编写的程序(毕竟所有的电脑程序都可以被表示为文本,对吧?)。\u003cbr\u003e证明这个定理非常简单。稍加计算就会发现,如果猴子打字的时间足够长,输出包含给定文本的概率将接近100%。\u003cbr\u003e然而,所需的时间太长,超出了物理上的合理范围。即使猴子打字直到宇宙的终结,也不可能产生任何有用的程序。为了验证这一点,并确保我们人类无法被猴子取代,你需要计算一下猴子成功打出正确文本的概率。\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"将会有多个测试用例。\u003cbr\u003e每个测试用例以包含两个整数 n 和 m 的一行开始,两个整数之间用空格分隔(2≤n≤26, 1≤m≤1000)。n 表示打字机上的键数,猴子将按下这些键 m 次。因此打字机最终会输出 m 个字符。\u003cbr\u003e接下来的 n 行描述了打字机上的键。每行包含一个小写字母和一个实数,两者之间用空格分隔。字母表示如果猴子按下该键,打字机会输出什么,实数表示猴子按下该键的概率。两次猴子按键是相互独立的(对于同一个键,两次不同的按键具有相同的概率),并且每个键的所有概率之和保证为1。\u003cbr\u003e测试用例的最后一行包含一个由小写字母组成的单词。该单词的长度将小于或等于10。\u003cbr\u003e输入以包含两个用空格分隔的零的一行结束。这一行不应被处理。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,输出一行,包含给定单词出现在打字机输出中的概率。输出应以百分比格式给出,数字应四舍五入到小数点后两位。"}},{"title":"样例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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 10\r\nw 0.25\r\no 0.25\r\nr 0.25\r\nd 0.25\r\nword\r\n2 10\r\na 1.0\r\nb 0.0\r\nabc\r\n2 100\r\na 0.312345\r\nb 0.687655\r\nabab\r\n0 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2.73%\r\n0.00%\r\n98.54%\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}