{"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\u003eIn typesetting, a “river” is a string of spaces formed by\n gaps between words that extends down several lines of text. For\n instance, Figure\u0026nbsp;1 shows several examples of rivers\n highlighted in red (text is intentionally blurred to make the\n rivers more visible).\u003c/p\u003e\n \u003cdiv id\u003d\"fig:rivers\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/f3ba07fffea2f99274bcfd0edd63fb6e?v\u003d1715002009\" alt\u003d\"\\includegraphics[width\u003d0.7\\textwidth ]{rivers4}\" style\u003d\"width:70.00%\"\u003e\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 1\u003c/b\u003e: Examples of rivers in typeset text.\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n \u003cp\u003eCelebrated river authority Flo Ng wants her new book on\n rivers of the world to include the longest typographic rivers\n possible. She plans to set the text in a mono-spaced font (all\n letters and spaces have equal width) in a left-aligned column\n of some fixed width, with exactly one space separating words on\n each line (the text is not aligned on the right). For Flo, a\n “river” is defined as a sequence of spaces lying in consecutive\n lines in which the position of each space in the sequence\n (except the first) differs by at most \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e from the position of the space in\n the line above it. Trailing white space cannot appear in a\n river. Words must be packed as tightly as possible on lines; no\n words may be split across lines. The line width used must be at\n least as long as the longest word in the text. For instance,\n Figure\u0026nbsp;2 shows the same text set with two different line\n widths.\u003c/p\u003e\n \u003cdiv id\u003d\"fig:lengths\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003ctable cellspacing\u003d\"0\" class\u003d\"tabular\"\u003e\n \u003ctbody\u003e\u003ctr\u003e\n \u003ctd style\u003d\"border-top-style:solid; border-left:1px solid black; border-right:1px solid black; border-top-color:black; border-top-width:1px; text-align:left\"\u003e\n \u003cp\u003e\u003cb class\u003d\"bfseries\"\u003eLine width 14: River of length\n 4\u003c/b\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:left; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003cb class\u003d\"bfseries\"\u003eLine width 15: River of length\n 5\u003c/b\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"border-top-style:solid; border-left:1px solid black; border-right:1px solid black; border-top-color:black; border-top-width:1px; text-align:left\"\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003eThe Yangtze is\u003cb class\u003d\"bfseries\"\u003e|\u003c/b\u003e\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:left; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003eThe Yangtze is\u0026nbsp;\u003cb class\u003d\"bfseries\"\u003e|\u003c/b\u003e\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"text-align:left; border-right:1px solid black; border-left:1px solid black\"\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003ethe\n third\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003cb class\u003d\"bfseries\"\u003e|\u003c/b\u003e\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:left; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003ethe\n third\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003cb class\u003d\"bfseries\"\u003e|\u003c/b\u003e\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"text-align:left; border-right:1px solid black; border-left:1px solid black\"\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003elongest river\u0026nbsp;\u003cb class\u003d\"bfseries\"\u003e|\u003c/b\u003e\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:left; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003elongest\u003cb class\u003d\"bfseries\"\u003e*\u003c/b\u003eriver\u0026nbsp;\u0026nbsp;\u003cb class\u003d\"bfseries\"\u003e|\u003c/b\u003e\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"text-align:left; border-right:1px solid black; border-left:1px solid black\"\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003ein\u003cb class\u003d\"bfseries\"\u003e*\u003c/b\u003eAsia and\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003cb class\u003d\"bfseries\"\u003e|\u003c/b\u003e\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:left; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003ein Asia\u003cb class\u003d\"bfseries\"\u003e*\u003c/b\u003eand the\u003cb class\u003d\"bfseries\"\u003e|\u003c/b\u003e\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"text-align:left; border-right:1px solid black; border-left:1px solid black\"\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003ethe\u003cb class\u003d\"bfseries\"\u003e*\u003c/b\u003elongest in\u003cb class\u003d\"bfseries\"\u003e|\u003c/b\u003e\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:left; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003elongest\u003cb class\u003d\"bfseries\"\u003e*\u003c/b\u003ein the\u0026nbsp;\u003cb class\u003d\"bfseries\"\u003e|\u003c/b\u003e\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"text-align:left; border-right:1px solid black; border-left:1px solid black\"\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003ethe\u003cb class\u003d\"bfseries\"\u003e*\u003c/b\u003eworld to\u0026nbsp;\u0026nbsp;\u003cb class\u003d\"bfseries\"\u003e|\u003c/b\u003e\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:left; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003eworld to\u003cb class\u003d\"bfseries\"\u003e*\u003c/b\u003eflow\u0026nbsp;\u0026nbsp;\u003cb class\u003d\"bfseries\"\u003e|\u003c/b\u003e\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"text-align:left; border-right:1px solid black; border-left:1px solid black\"\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003eflow\u003cb class\u003d\"bfseries\"\u003e*\u003c/b\u003eentirely\u0026nbsp;\u003cb class\u003d\"bfseries\"\u003e|\u003c/b\u003e\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:left; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003eentirely\u003cb class\u003d\"bfseries\"\u003e*\u003c/b\u003ein one\u003cb class\u003d\"bfseries\"\u003e|\u003c/b\u003e\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"border-bottom-style:solid; border-bottom-width:1px; border-left:1px solid black; border-right:1px solid black; text-align:left; border-bottom-color:black\"\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003ein one country\u003cb class\u003d\"bfseries\"\u003e|\u003c/b\u003e\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-bottom-color:black; border-bottom-width:1px; text-align:left; border-bottom-style:solid; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt class\u003d\"ttfamily\"\u003ecountry\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003cb class\u003d\"bfseries\"\u003e|\u003c/b\u003e\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\u003c/table\u003e\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 2\u003c/b\u003e: Longest rivers (\u003ctt class\u003d\"ttfamily\"\u003e\u003cb class\u003d\"bfseries\"\u003e*\u003c/b\u003e\u003c/tt\u003e) for two\n different line widths.\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n \u003cp\u003eGiven a text, you have been tasked with determining the line\n width that produces the longest river of spaces for that\n text.\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe first line of input contains an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$2\n \\leq n \\leq 2\\, 500$\u003c/span\u003e) specifying the number of words in\n the text. The following lines of input contain the words of\n text. Each word consists only of lowercase and uppercase\n letters, and words on the same line are separated by a single\n space. No word exceeds \u003cspan class\u003d\"tex2jax_process\"\u003e$80$\u003c/span\u003e characters.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eDisplay the line width for which the input text contains the\n longest possible river, followed by the length of the longest\n river. If more than one line width yields this maximum, display\n the shortest such line width.\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\u003e21\nThe Yangtze is the third longest\nriver in Asia and the longest in\nthe world to flow\nentirely in one country\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e15 5\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\u003e25\nWhen two or more rivers meet at\na confluence other than the sea\nthe resulting merged river takes\nthe name of one of those rivers\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e21 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 "}}]}