{"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 div.sampleinteractionread {\n width: 60%;\n margin: 3px 0px 3px 0px;\n }\n div.sampleinteractionread pre {\n margin: 1px 5px 1px 5px;\n border-radius: 5px;\n border: solid 1px rgba(255, 255, 255, 0.25);\n background-color: #cccccc;\n padding: 14px 13px;\n font-family: Courier, monospace;\n font-variant-ligatures: none;\n }\n div.sampleinteractionwrite {\n width: 60%;\n margin: 3px 0px 3px 0px;\n margin-left: auto;\n }\n div.sampleinteractionwrite pre {\n margin: 1px 5px 1px 5px;\n border-radius: 5px;\n border: solid 1px rgba(255, 255, 255, 0.25);\n background-color: #cccccc;\n padding: 14px 13px;\n font-family: Courier, monospace;\n font-variant-ligatures: none;\n }\n table.sample {\n width: 100%;\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:32.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/f0cd1a6522cf0e72870e4597228e626f?v\u003d1721896928\" alt\u003d\"/problems/inflation/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n \n \u003c/div\u003eFor NWERC 2018, the organisers have done something rather\n special with the balloons. Instead of buying balloons of equal\n size, they bought one balloon of every integer size from\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e up to \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e. A balloon of size \u003cspan class\u003d\"tex2jax_process\"\u003e$s$\u003c/span\u003e has a capacity of \u003cspan class\u003d\"tex2jax_process\"\u003e$s$\u003c/span\u003e decilitres.\n \u003cp\u003eTo avoid inflating the balloons by hand, the organisers also\n bought \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e helium gas\n canisters. Each canister can only be used to inflate one\n balloon, and must be emptied completely into that balloon (it\n is not possible to disconnect a canister from a balloon before\n the canister has been fully used).\u003c/p\u003e\n \u003cp\u003eUnfortunately the gas canisters were bought at a garage\n sale, and may contain differing amounts of helium. Some may\n even be empty! To make the best of this challenging situation,\n the canisters will have to be paired with the balloons\n smartly.\u003c/p\u003e\n \u003cp\u003eThe organisers want to assign all of the gas canisters to\n separate balloons, such that the balloon that is inflated the\n least (relative to its capacity) still contains the maximum\n possible fraction of helium inside. What is the maximum such\n (minimum) fraction that is possible?\u003c/p\u003e\n \u003cp\u003eBalloons filled beyond their capacity will explode.\n Explosions are upsetting and must be avoided.\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe input consists of:\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eOne line with the integer \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le n \\le 2\\cdot 10^5$\u003c/span\u003e), the\n number of balloons and gas canisters.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eOne line with \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e\n integers \u003cspan class\u003d\"tex2jax_process\"\u003e$c_1, \\ldots , c_\n n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\le c_ i \\le\n n$\u003c/span\u003e for each \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e), the amounts of helium in the\n gas canisters, in decilitres.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eIf it is possible to fill all the balloons without any\n exploding, output the maximum fraction \u003cspan class\u003d\"tex2jax_process\"\u003e$f$\u003c/span\u003e such that every balloon can be\n filled to at least \u003cspan class\u003d\"tex2jax_process\"\u003e$f$\u003c/span\u003e of\n its capacity. Otherwise, output ā\u003ctt class\u003d\"ttfamily\"\u003eimpossible\u003c/tt\u003eā.\u003c/p\u003e\n \u003cp\u003eYour answer should have an absolute or relative error of at\n 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\u003e6\n6 1 3 2 2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0.6\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\u003e2\n2 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eimpossible\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\n4 0 2 1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}