{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:50.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/5506a171396a8ba3253ef4311d6b2639?v\u003d1715181639\" alt\u003d\"/problems/arcade/file/statement/en/img-0001.png\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003eHave you recently visited an arcade? Arcade games seem to\n have become more boring over the years, requiring less and less\n skill. In fact, most arcade games these days seem to depend\n entirely on luck. Consider the arcade game shown in the\n picture, which consists of different holes arranged in a\n triangular shape. A ball is dropped near the hole at the top.\n The ball either falls into the hole, in which case the game\n ends, or it bounces to one of its (up to) \u003cspan class\u003d\"tex2jax_process\"\u003e$4$\u003c/span\u003e neighbors, denoted by the red\n arrows. Different holes have different payouts — some may even\n be negative! If the ball reaches another hole, the process\n repeats: the ball either falls into the hole, ending the game —\n or it bounces to one of its neighbors, possibly ad infinitum!\n\n \u003cp\u003eWrite a program that computes the expected payout when\n dropping a ball into the machine!\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe input consists of a single test case. The first line\n contains an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e\n (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le N \\le 32$\u003c/span\u003e)\n describing the number of rows of the arcade machine. The second\n line contains \u003cspan class\u003d\"tex2jax_process\"\u003e$H \u003d N (N+1) /\n 2$\u003c/span\u003e integers \u003cspan class\u003d\"tex2jax_process\"\u003e$v_ i$\u003c/span\u003e\n (\u003cspan class\u003d\"tex2jax_process\"\u003e$-100 \\le v_ i \\le 100$\u003c/span\u003e)\n describing the payout (positive or negative) if the ball drops\n into hole \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e. Holes are\n numbered such that hole \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e is in the first row, holes\n \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e are in the second row, etc. The\n \u003cspan class\u003d\"tex2jax_process\"\u003e$k^{\\textrm{th}}$\u003c/span\u003e row\n starts with hole number \u003cspan class\u003d\"tex2jax_process\"\u003e$k (k-1)\n / 2 + 1$\u003c/span\u003e and contains exactly \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e holes.\u003c/p\u003e\n\n \u003cp\u003eThese two lines are followed by \u003cspan class\u003d\"tex2jax_process\"\u003e$H$\u003c/span\u003e lines, each of which contains\n \u003cspan class\u003d\"tex2jax_process\"\u003e$5$\u003c/span\u003e real numbers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$p_0 \\ p_1 \\ p_2 \\ p_3 \\\n p_4$\u003c/span\u003e, denoting the probability that the ball bounces to\n its top-left (\u003cspan class\u003d\"tex2jax_process\"\u003e$p_0$\u003c/span\u003e),\n top-right (\u003cspan class\u003d\"tex2jax_process\"\u003e$p_1$\u003c/span\u003e),\n bottom-left (\u003cspan class\u003d\"tex2jax_process\"\u003e$p_2$\u003c/span\u003e), or\n bottom-right (\u003cspan class\u003d\"tex2jax_process\"\u003e$p_3$\u003c/span\u003e)\n neighbors or that the ball enters the hole (\u003cspan class\u003d\"tex2jax_process\"\u003e$p_4$\u003c/span\u003e). Each probability is given with\n at most \u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e decimal digits\n after the period. It is guaranteed that \u003cspan class\u003d\"tex2jax_process\"\u003e$0.0 \\le p_ i \\le 1.0$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$\\sum p_ i \u003d 1.0$\u003c/span\u003e. If a\n hole does not have certain neighbors because it is located near\n the boundary of the arcade machine, the probability of bouncing\n to these non-existent neighbors is always zero. For instance,\n for hole number \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e, the\n probabilities to jump to the top-left and top-right neighbors\n are both given as \u003cspan class\u003d\"tex2jax_process\"\u003e$0.0$\u003c/span\u003e.\u003c/p\u003e\n\n \u003cp\u003eYou can assume that after the ball has bounced \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e times, the probability that it has\n not fallen into a hole is at most \u003cspan class\u003d\"tex2jax_process\"\u003e$(1 - 10^{-3})^{\\lfloor b/H \\rfloor\n }$\u003c/span\u003e.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eOutput a single number, the expected value from playing one\n game. Your answer is considered correct if its absolute or\n relative error is less than \u003cspan class\u003d\"tex2jax_process\"\u003e$10^{-4}$\u003c/span\u003e.\u003c/p\u003e\n\n \u003cp\u003e\u003cem\u003eHint:\u003c/em\u003e Using Monte Carlo-style simulation (throwing\n many balls in the machine and simulating which hole they fall\n into using randomly generated choices) does not yield the\n required accuracy!\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\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\n40 30 30 40 20 40 50 30 30 50\n0.0 0.0 0.45 0.45 0.1\n0.0 0.3 0.3 0.3 0.1\n0.3 0.0 0.3 0.3 0.1\n0.0 0.3 0.3 0.3 0.1\n0.2 0.2 0.2 0.2 0.2\n0.3 0.0 0.3 0.3 0.1\n0.0 0.8 0.0 0.0 0.2\n0.4 0.4 0.0 0.0 0.2\n0.4 0.4 0.0 0.0 0.2\n0.8 0.0 0.0 0.0 0.2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e32.6405451448\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\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\u003e2\n100 50 50\n0.0 0.0 0.45 0.45 0.1\n0.0 0.90 0.0 0.0 0.10\n0.90 0.0 0.0 0.0 0.10\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e76.31578947368\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}