{"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\u003eAlaa fondly remembers playing with a construction toy when\n she was a child. It consisted of segments that could be\n fastened at each end. A game she liked to play was to start\n with one segment as a base, placed flat against a straight\n wall. Then she repeatedly added on triangles, with one edge of\n the next triangle being a single segment already in place on\n her structure, and the other two sides of the triangle being\n newly added segments. She only added real triangles: never with\n the sum of the lengths of two sides equaling the third. Of\n course no segment could go through the wall, but she did allow\n newly added segments to cross over already placed ones. Her aim\n was to see how far out from the wall she could make her\n structure go. She would experiment, building different ways\n with different combinations of some or all of her pieces. It\n was an easy, boring task if all the segments that she used were\n the same length! It got more interesting if she went to the\n opposite extreme and started from a group of segments that were\n all of distinct lengths.\u003c/p\u003e\n\n \u003cp\u003eFor instance, the figures below illustrate some of the\n structures she could have built with segments of length\n \u003cspan class\u003d\"tex2jax_process\"\u003e$42$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$40$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$32$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$30$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$25$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$18$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$15$\u003c/span\u003e, including one that reaches a\n maximum distance of \u003cspan class\u003d\"tex2jax_process\"\u003e$66.9495$\u003c/span\u003e from the wall.\u003c/p\u003e\n\n \u003cdiv id\u003d\"first\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003ctable class\u003d\"subfigure\" id\u003d\"a0000000006\" style\u003d\"display:inline-table\"\u003e\n \u003ctbody\u003e\u003ctr\u003e\n \u003ctd\u003e\u003cimg src\u003d\"CDN_BASE_URL/901aebf39f86c0b6d5b81584b3700d45?v\u003d1715589991\" alt\u003d\"\\includegraphics[scale\u003d0.5]{figures/bad_42_40_32_30_25_18_15.png}\" style\u003d\"width:; height:\"\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\n \u003ctr\u003e\n \u003ctd style\u003d\"text-align:center\"\u003e(1.a)\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\u003c/table\u003e \n\n \u003ctable class\u003d\"subfigure\" id\u003d\"a0000000007\" style\u003d\"display:inline-table\"\u003e\n \u003ctbody\u003e\u003ctr\u003e\n \u003ctd\u003e\u003cimg src\u003d\"CDN_BASE_URL/d02e2e423a85a9c4da361a2545479c2e?v\u003d1715589991\" alt\u003d\"\\includegraphics[scale\u003d0.5]{figures/better_42_40_32_30_25_18_15.png}\" style\u003d\"width:; height:\"\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\n \u003ctr\u003e\n \u003ctd style\u003d\"text-align:center\"\u003e(1.b)\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\u003c/table\u003e \n\n \u003ctable class\u003d\"subfigure\" id\u003d\"a0000000008\" style\u003d\"display:inline-table\"\u003e\n \u003ctbody\u003e\u003ctr\u003e\n \u003ctd\u003e\u003cimg src\u003d\"CDN_BASE_URL/27aa7836824c1e18c3ad61c06ca83e0f?v\u003d1715589991\" alt\u003d\"\\includegraphics[scale\u003d0.5]{figures/best_42_40_32_30_25_18_15.png}\" style\u003d\"width:; height:\"\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\n \u003ctr\u003e\n \u003ctd style\u003d\"text-align:center\"\u003e(1.c)\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\u003c/table\u003e\n\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 1\u003c/b\u003e: Candidate constructions for example\n lengths, with the wall at left in each\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n\n \u003cp\u003eNow, looking back as a Computer Science student, Alaa\n wondered how well she did, so she has decided to write a\n program to compute the maximum distance given a set of segment\n lengths.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe input is a single line of positive integers. The first\n integer \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e designates the\n number of segments, with \u003cspan class\u003d\"tex2jax_process\"\u003e$3 \\leq\n n \\leq 9$\u003c/span\u003e. The following \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e integers, \u003cspan class\u003d\"tex2jax_process\"\u003e$\\ell _1 \u0026gt; \\ell _2 \u0026gt; \\cdots \u0026gt; \\ell _\n n$\u003c/span\u003e designate the lengths of the segments, such that\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq \\ell _ j \\leq 99$\u003c/span\u003e\n for all \u003cspan class\u003d\"tex2jax_process\"\u003e$j$\u003c/span\u003e. The lengths\n will permit at least one triangle to be constructed.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eOutput is the maximum distance that one of Alaa’s structures\n can reach away from the wall, stated with a relative or\n absolute error of at most \u003cspan class\u003d\"tex2jax_process\"\u003e$10^{-2}$\u003c/span\u003e. The input data is chosen so\n that any structure acheiving the maximum distance has all\n vertices except the base vertices at least \u003cspan class\u003d\"tex2jax_process\"\u003e$0.0001$\u003c/span\u003e from the wall.\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\u003e3 50 40 30\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e40\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\u003e4 50 40 30 29\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e40\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 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\u003e7 42 40 32 30 25 18 15\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e66.9495287\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}