{"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:20.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/92b289f95f64cd635b0fc92219f7ecaa?v\u003d1714285886\" alt\u003d\"/problems/bridgeautomation/file/statement/en/img-0001.png\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003e\n\n \u003cp\u003eIn Delft there are a number of bridges that are still being\n operated by a human, known as the bridge operator. One such\n bridge operator will soon retire, hence there is the need for a\n replacement. The Bridge And Poker Committee has decided to use\n a computer program to automatically open and close the bridge,\n eliminating the need for human interaction.\u003c/p\u003e\n\n \u003cp\u003eHowever, the computer program still needs to be written. The\n requirements for this project are as follows:\u003c/p\u003e\n\n \u003col class\u003d\"enumerate\"\u003e\n \u003cli\u003e\n \u003cp\u003eNo boat may be forced to wait for more than \u003cspan class\u003d\"tex2jax_process\"\u003e$30$\u003c/span\u003e minutes.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eThe amount of time during which the bridge is\n unavailable to road traffic must be as small as possible\n while still satisfying requirement 1.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ol\u003e\n\n \u003cp\u003eIt takes \u003cspan class\u003d\"tex2jax_process\"\u003e$60$\u003c/span\u003e seconds\n to raise or lower the bridge. During this time the bridge is\n not available to either road traffic or water traffic.\u003c/p\u003e\n\n \u003cp\u003eBoats arrive at the bridge at predictable times. It takes\n \u003cspan class\u003d\"tex2jax_process\"\u003e$20$\u003c/span\u003e seconds for a boat to\n sail through the bridge, assuming the bridge is already fully\n raised.\u003c/p\u003e\n\n \u003cp\u003eIf the bridge is not fully raised when a boat arrives, the\n boat must wait. If there are boats waiting when the bridge\n becomes fully raised, these boats pass through the bridge\n one-by-one, which takes \u003cspan class\u003d\"tex2jax_process\"\u003e$20$\u003c/span\u003e seconds per boat. The bridge must\n remain fully raised as long as there are still boats sailing\n through! As soon as all boats have passed, the bridge may be\n lowered. But it might be more efficient to keep the bridge\n raised for a little while longer if the next boat is soon to\n arrive.\u003c/p\u003e\n\n \u003cp\u003eGiven the arrival times of all boats, operate the bridge\n such that all boats can pass through without any boat waiting\n longer than \u003cspan class\u003d\"tex2jax_process\"\u003e$30$\u003c/span\u003e minutes.\n What is the total amount of time during which the bridge is\n unavailable to road traffic?\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe first line contains an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e, the number of boats that must\n pass the bridge (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq N \\leq\n 4\\, 000$\u003c/span\u003e).\u003c/p\u003e\n\n \u003cp\u003eThen follow \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e lines,\n each containing an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$T_\n i$\u003c/span\u003e, the time at which boat \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e will arrive at the bridge in\n seconds (\u003cspan class\u003d\"tex2jax_process\"\u003e$60 \\leq T_ i \\leq\n 10^5$\u003c/span\u003e).\u003c/p\u003e\n\n \u003cp\u003eBoats are sorted by increasing time of arrival, and never\n arrive within \u003cspan class\u003d\"tex2jax_process\"\u003e$20$\u003c/span\u003e seconds\n of each other (\u003cspan class\u003d\"tex2jax_process\"\u003e$i \u0026lt; j$\u003c/span\u003e\n implies \u003cspan class\u003d\"tex2jax_process\"\u003e$T_ i + 20 \\leq T_\n j$\u003c/span\u003e).\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eWrite one line with an integer, the total number of seconds\n during which the bridge must be unavailable for road traffic in\n order for all boats to pass the bridge.\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\u003e2\n100\n200\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e160\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\u003e3\n100\n200\n2010\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e250\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\u003e3\n100\n200\n2100\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e300\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}