Text Formatting
InterviewTime limit2sMemory limit512 MB
Reformat a text into paragraphs, each indented by b spaces and wrapped greedily at width w, with punctuation glued to the preceding word.
- Level
Medium5 of 10
- Topics
- String, Simulation, Implementation, Greedy
- Solved
- No attempts yet
Problem
Many text formatting systems, such as TEX or Wiki, use blank lines to split text into paragraphs. A text is a sequence of words separated by spaces, newline characters, and the following punctuation marks: ,, ., ?, !, -, :, and ' (ASCII codes 44, 46, 63, 33, 45, 58, 39). Each word in the text consists of uppercase and lowercase letters of the Latin alphabet and digits. A text may consist of several paragraphs. In that case, adjacent paragraphs are separated by one or more blank lines. Before the first paragraph and after the last paragraph, there may also be one or more blank lines.
Further use of the source text assumes its formatting, which is carried out as follows. Each paragraph must be split into lines, each of which has length at most w. The first line of each paragraph must begin with an indent consisting of b spaces. Words within one line must be separated by exactly one space. If one or more punctuation marks follow a word, they must follow the word immediately without extra spaces. If the next word together with the punctuation marks following it fits on the current line, it is placed on the current line. Otherwise, a new line starts with this word. In the formatted text, paragraphs must not be separated by blank lines. There must be no spaces at the ends of lines.
Write a program that, given the numbers w and b and the given text, outputs the text formatted as described above.
Input
The first line of the input file contains two integers: w and b (5 ≤ w ≤ 100, 1 ≤ b ≤ 8, b < w).
Then follows one or more lines containing the given text. The length of a word in the text together with the punctuation marks following it does not exceed w, and the length of the first word of any paragraph together with the punctuation marks following it does not exceed (w – b).
The size of the input file does not exceed 100 KB. The length of each line in the input file does not exceed 250.
Output
The output file must contain the given text formatted according to the rules given in the problem statement.