{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"You are in a maze; in front of you there are **n** doors . You can choose to go through any door you like. The probability for choosing a door is equal for all doors.\n\nIf you choose the **i\u003csup\u003eth\u003c/sup\u003e** door, it can either take you back to the same position where you began in **x\u003csub\u003ei\u003c/sub\u003e** minutes, or can take you out of the maze after **x\u003csub\u003ei\u003c/sub\u003e** minutes. If you come back to the same position, you can remember the last **K** doors you have chosen. And when you are about to choose a door, you never choose a door that is already visited by you. Or we can say that you never choose a door that is visited as one of the last **K** doors. And the probability of choosing any remaining doors is equal.\n\nNow you want to find the expected time to get out of the maze."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026#8804; 100)**, denoting the number of test cases.\n\nEach case contains a blank line and two integers **n K (1 \u0026#8804; n \u0026#8804; 100, 0 \u0026#8804; K \u0026#8804; n)**. The next line contains **n** space separated integers. If the **i\u003csup\u003eth\u003c/sup\u003e** integer **(x\u003csub\u003ei\u003c/sub\u003e)** is positive, you can assume that the **i\u003csup\u003eth\u003c/sup\u003e** door will take you out of maze after **x\u003csub\u003ei\u003c/sub\u003e** minutes. If it\u0027s negative, then the **i\u003csup\u003eth\u003c/sup\u003e** door will take you back to the beginning position after **abs(x\u003csub\u003ei\u003c/sub\u003e)** minutes. You can safely assume that **1 \u0026#8804; abs(x\u003csub\u003ei\u003c/sub\u003e) \u0026#8804; 10000**."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the expected time to get out of the maze. If it\u0027s impossible to get out of the maze, print `-1`. Otherwise, print the result. Error less than **10\u003csup\u003e-6\u003c/sup\u003e** will be ignored."}},{"title":"Sample","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\n\n2 0\n10 10\n\n2 0\n10 -10\n\n3 1\n10 -10 -20\n\n3 2\n10 -10 -20\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 10\nCase 2: 20.000\nCase 3: 30.0000000000\nCase 4: 25.0000000000\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}