{"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:30.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/57ec69a7d0aa5238c492fa0defe44480?v\u003d1715664337\" alt\u003d\"/problems/researchproductivityindex/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n \n \u003c/div\u003eAngela is a new PhD student and she is nervous about the\n upcoming paper submission deadline of this year’s research\n conference. She has been working on multiple projects\n throughout the past year. Luckily most of the projects\n concluded successfully, and she came up with \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e candidate papers. However not all\n of the papers were born equal—some have better results than\n others. Her advisor believes she should only submit the papers\n with “good enough” results so they have a high chance of\n getting accepted.\n \u003cp\u003eAngela’s research group has a unique way of evaluating the\n success of paper submissions. They use the \u003cem\u003eresearch\n productivity index\u003c/em\u003e, defined as \u003cspan class\u003d\"tex2jax_process\"\u003e$a^{a/s}$\u003c/span\u003e, where \u003cspan class\u003d\"tex2jax_process\"\u003e$s$\u003c/span\u003e is the total number of papers\n submitted, and \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e is the\n number of papers that are accepted by the conference. When\n \u003cspan class\u003d\"tex2jax_process\"\u003e$a \u003d 0$\u003c/span\u003e, the index is\n defined to be zero. For example:\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eif one paper is submitted and it gets accepted, the\n index is \u003cspan class\u003d\"tex2jax_process\"\u003e$1^{1/1} \u003d\n 1$\u003c/span\u003e;\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eif \u003cspan class\u003d\"tex2jax_process\"\u003e$4$\u003c/span\u003e papers are\n submitted and all get accepted, the index is \u003cspan class\u003d\"tex2jax_process\"\u003e$4^{4/4} \u003d 4$\u003c/span\u003e;\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eif \u003cspan class\u003d\"tex2jax_process\"\u003e$10$\u003c/span\u003e papers are\n submitted and \u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e get\n accepted, the index is \u003cspan class\u003d\"tex2jax_process\"\u003e$3^{3/10} \\approx 1.390389$\u003c/span\u003e;\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eif \u003cspan class\u003d\"tex2jax_process\"\u003e$5$\u003c/span\u003e papers are\n submitted and \u003cspan class\u003d\"tex2jax_process\"\u003e$4$\u003c/span\u003e get\n accepted, the index is \u003cspan class\u003d\"tex2jax_process\"\u003e$4^{4/5} \\approx 3.031433$\u003c/span\u003e;\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eif \u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e papers are\n submitted and all get rejected (\u003cspan class\u003d\"tex2jax_process\"\u003e$a\u003d0$\u003c/span\u003e), the index is \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003cp\u003eIntuitively, to get a high research productivity index one\n wants to get as many papers accepted as possible while keeping\n the acceptance rate high.\u003c/p\u003e\n \u003cp\u003eFor each of her \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e\n papers, Angela knows exactly how likely it is that the\n conference would accept the paper. If she chooses wisely which\n papers to submit, what is the maximum expected value of her\n research productivity index?\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe first line of the input has a single integer\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq n \\leq 100$\u003c/span\u003e), the number of\n Angela’s candidate papers. The next line has \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e space-separated integers giving\n the probability of each paper getting accepted. Each\n probability value is given as an integer percentage between\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$100$\u003c/span\u003e, inclusive.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eOutput the maximum expected value of Angela’s research\n productivity index. Your answer is considered correct if it has\n an absolute or relative error of no more than \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\u003e5\n30 50 70 60 90\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2.220889579\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\u003e6\n30 90 30 90 30 90\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2.599738456\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\u003e4\n10 10 10 10\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0.368937005\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}