{"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/bdff15ed6760fe17ddc1aa042d96aea0?v\u003d1719244546\" alt\u003d\"/problems/graduationguarantee/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n \n \u003c/div\u003e\n \u003cp\u003eGustav is studying to become an interpreter. In this line of\n work, knowing several languages is a must, and Gustav is\n already fluent in French, Mandarin, Nahuatl and even Finnish.\n But there is one language that Gustav struggles with:\n Norwegian. Before Gustav can graduate, he must complete the\n infamous Norwegian Conclusive Proficiency Check.\u003c/p\u003e\n \u003cp\u003eThis exam consists of \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e yes/no questions. Answering\n correctly gives \u003cspan class\u003d\"tex2jax_process\"\u003e$+1$\u003c/span\u003e\n point, answering incorrectly gives \u003cspan class\u003d\"tex2jax_process\"\u003e$-1$\u003c/span\u003e point, and not answering gives\n \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e points. To pass the\n exam, at least \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e points\n are needed. For each question, Gustav has a guess that he knows\n is correct with probability \u003cspan class\u003d\"tex2jax_process\"\u003e$p_\n i$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$0.5 \\leq p_ i \\leq\n 1$\u003c/span\u003e). Note that \u003cspan class\u003d\"tex2jax_process\"\u003e$p_ i \\geq\n 0.5$\u003c/span\u003e, because otherwise guessing the opposite would be\n better.\u003c/p\u003e\n \u003cp\u003eWhat is the maximum possible probability of passing the\n exam, assuming we carefully choose which questions to answer\n and which ones to leave unanswered? Note that unlike a\n programming contest, the exam does not have instant feedback.\n So Gustav will answer the questions, hand in his answers, and\n only later be told the results.\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe first line contains the two integers \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\leq k \\leq n \\leq 5000$\u003c/span\u003e). The second line contains\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e real numbers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$p_ i$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$0.5 \\leq p_ i \\leq 1.0$\u003c/span\u003e). These\n numbers will have at most \u003cspan class\u003d\"tex2jax_process\"\u003e$6$\u003c/span\u003e digits after the decimal\n point.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eOutput the probability that we pass the exam. Your answer\n will be considered correct if it has an absolute or relative\n 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\u003e3 3\n0.5 0.5 0.5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0.125\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\u003e4 1\n0.9 0.5 0.9 0.9\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0.972\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}