{"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/899fb8f4f7882cc32dfb5bd26348cf78?v\u003d1715760190\" alt\u003d\"/problems/freeweights/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003e\n\n \u003cp\u003eThe city of Bath is a noted olympic training ground—bringing\n local, national, and even international teams to practice.\n However, even the finest gymnasium falls victim to the cardinal\n sin…Weights put back in the wrong spots.\u003c/p\u003e\n\n \u003cp\u003eAll of the pairs of dumbbells sit in no particular order on\n the two racks, possibly even with some of them split between\n rows. Initially each row has an equal number of dumbbells,\n however, this being a well-funded professional gym, there is\n infinite space at either end of each to hold any additional\n weights.\u003c/p\u003e\n\n \u003cp\u003eTo move a dumbbell, you may either roll it to a free\n neighbouring space on the same row with almost no effort, or\n you may pick up and lift it to another free spot; this takes\n strength proportional to its weight. For each pair of\n dumbbells, both have the same unique weight.\u003c/p\u003e\n\n \u003cp\u003eWhat is the heaviest of the weights that you need to be able\n to lift in order to put identical weights next to each other?\n Note that you may end up with different numbers of weights on\n each row after rearranging; this is fine.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe input consists of:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eone line containing the integer \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le n \\le 10^6$\u003c/span\u003e), the number of\n pairs;\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003etwo lines, each containing \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e integers \u003cspan class\u003d\"tex2jax_process\"\u003e$w_1 \\ldots w_ n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le w_ i \\le 10^9$\u003c/span\u003e for each\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e), where\n \u003cspan class\u003d\"tex2jax_process\"\u003e$w_ i$\u003c/span\u003e is the mass of\n the weight \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e-th from\n the left along this row.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003cp\u003eEvery weight in the input appears exactly twice.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eOutput the weight of the heaviest dumbbell that must be\n moved, in order that all items can be paired up while lifting\n the smallest possible maximum weight.\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\u003e5\n2 1 8 2 8\n9 9 4 1 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\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\u003e8\n7 7 15 15 2 2 4 4\n5 5 3 3 9 9 1 1\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 "}}]}