Problem E
Elder Scrollbar

A window with scrollbar from more recent times. License, public domain.

When the first scrollbars appeared on resizable windows during user interface development in the Elder Days, computer graphics were still primitive. Widgets were made with ASCII symbols and text was monospaced. A window displayed a viewport: a part of a much longer text, adjusted to fit the width of the window. The thumb, shown as an X, represented the position of the viewport relative to the full (adjusted) text and allowed vertical nagivation by clicking and dragging.

Alas, much of the knowledge of the Ancients has been lost in the Great Purge of the Second Iconoclast Uprising, which destroyed the last remaining implementations of the user interface layer of the Elder GUI. As head programmer of the National Laboratory of Interaction Design Archeology it is your job to recreate the behaviour of the machines of yore as faithfully as possible.

Thanks to many years of studies, you have full understanding of the typographical aesthetics of the Elder Days: Lines were set flush left but ragged-right, and words on the same line were separated by single spaces. Line breaking was simple in those days: When the next word of the text fit on the current line, it was put there, otherwise a new line was started. If a word was too wide to fit the viewport, it was set on a line of its own and truncated at the right margin.

The language of the Ancients was written in upper- and lowercase letters of the English alphabet without punctuation or hyphenation. The scroll bar on the right contained navigation widgets for “up” and “down” at the top and bottom.


The first line consists of $4$ integers $W$, $H$, $F$, $N$, separated by single spaces. The width of the viewport is $W$, with $3\leq W\leq 200$. The height of the viewport is $H$, with $3\leq H\leq 200$. The viewport must show line $F$ of the adjusted input as the first line at the top line; lines are numbered $0,\ldots , L-1$, where $L$ is the total number of lines in the adjusted text; you can assume $0\leq F \leq L - H$ and $H < L$. The following $N$ lines for $1\leq N\leq 30\, 000$ contain the text (not adjusted), between $1$ and $80$ characters per line, including spaces; neither the first nor last character in each line are a space. No word in the language of the Ancients was more than $80$ characters.

Thumb position

You have discovered many ancient texts explaining the position $T\in \{ 0,\ldots , H-3\} $ of the thumb. Alas, all are written in arcane languages that are long forgotten. One example reads like this:


Another source claims that $T$ can be determined by an incantation that is almost poetic in its mystery,

 H 3 - F *  L H - /

and yet another obscure author writes

(defun thumb (lines height first) (/ (* (- height 3) first) (- lines height)))


Print the window as the Ancients would have seen it, built from minus (-), plus (+), pipe (|), lower-case V (v), caret (^), and upper-case X (X). See the sample output for the details.

Sample Input 1 Sample Output 1
24 5 8 7
Lorem ipsum dolor sit amet consectetur adipisicing elit sed do
eiusmod tempor incididunt ut labore et dolore magna aliqua Ut enim ad
minim veniam quis nostrud exercitation ullamco laboris nisi ut
aliquip ex ea commodo consequat Duis aute irure dolor in
reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla
pariatur Excepteur sint occaecat cupidatat non proident sunt in
culpa qui officia deserunt mollit anim id est laborum
|exercitation ullamco    |^|
|laboris nisi ut aliquip | |
|ex ea commodo consequat |X|
|Duis aute irure dolor in| |
|reprehenderit in        |v|
Sample Input 2 Sample Output 2
8 6 1 1
Lorem ipsum dolor sit amet consectetur adipisicing elit sed do
|ipsum   |^|
|dolor   | |
|sit amet|X|
|consecte| |
|adipisic| |
|elit sed|v|
CPU Time limit 2 seconds
Memory limit 1024 MB
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in