{"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 \u003cp\u003eGem Island is a tiny island in the middle of the Pacific\n Ocean. Until recently, it was known as one of the poorest, but\n also most peaceful, places on Earth. Today, it is neither poor\n nor peaceful. What happened?\u003c/p\u003e\n \u003cp\u003eOne sunny morning, not too long ago, all inhabitants of Gem\n Island woke up to a surprise. That morning, each of them\n suddenly held one sparkling gem in their hand. The gems had\n magically appeared overnight. This was cause for much rejoicing\n – everybody was suddenly rich, they could finally afford all\n the things they had ever dreamed of, and the name of their\n island made so much more sense now.\u003c/p\u003e\n \u003cp\u003eThe next morning, one of the inhabitants woke up to another\n surprise – her gem had magically split into two gems! The same\n thing happened on each of the following nights, when exactly\n one of the gems (apparently uniformly at random among all the\n gems on the island) would split into two.\u003c/p\u003e\n \u003cp\u003eAfter a while, the inhabitants of Gem Island possessed a\n widely varying number of gems. Some had a lot and many had only\n a few. How come some inhabitants had more gems than others? Did\n they cheat, were they just lucky, or was something else at\n work?\u003c/p\u003e\n \u003cp\u003eThe island elders have asked for your help. They want you to\n determine if the uneven distribution of gems is explained by\n pure chance. If so, that would greatly reduce tensions on the\n island.\u003c/p\u003e\n \u003cp\u003eThe island has \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e\n inhabitants. You are to determine the gem distribution after\n \u003cspan class\u003d\"tex2jax_process\"\u003e$d$\u003c/span\u003e nights of gem\n splitting. In particular, you are interested in the expected\n number of gems collectively held by the \u003cspan class\u003d\"tex2jax_process\"\u003e$r$\u003c/span\u003e people with the largest numbers of\n gems. More formally, suppose that after \u003cspan class\u003d\"tex2jax_process\"\u003e$d$\u003c/span\u003e nights the numbers of gems held by\n the \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e inhabitants are\n listed in non-increasing order as \u003cspan class\u003d\"tex2jax_process\"\u003e$a_1 \\ge a_2 \\ge \\ldots \\ge a_ n$\u003c/span\u003e.\n What is the expected value of \u003cspan class\u003d\"tex2jax_process\"\u003e$a_1 + \\dots + a_ r$\u003c/span\u003e?\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe input consists of a single line containing the three\n integers \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$d$\u003c/span\u003e, and \u003cspan class\u003d\"tex2jax_process\"\u003e$r$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\leq n, d \\leq 500$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\leq r \\leq n$\u003c/span\u003e), as described in the problem statement\n above.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eDisplay the expected number of gems that the top\n \u003cspan class\u003d\"tex2jax_process\"\u003e$r$\u003c/span\u003e inhabitants hold after\n \u003cspan class\u003d\"tex2jax_process\"\u003e$d$\u003c/span\u003e nights, with an\n absolute or relative error of at most \u003cspan class\u003d\"tex2jax_process\"\u003e$10^{-6}$\u003c/span\u003e.\u003c/p\u003e\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\u003e2 3 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3.5\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\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\u003e3 3 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4.9\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 3\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\u003e5 10 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e12.2567433\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}