Word wrapping P59168


Statement
 

pdf   zip

thehtml

Word wrapping is breaking a text into lines so that they fit into the width w of a page. For simplicity, suppose that the text has only n words [t0, …, tn−1] without punctuation marks. If we decide to include the words [ti, …, tj] separated with spaces in the k-th line, and the sum of lengths of those words is ℓ, then we will use ℓ + ji characters. Hence, we will have exactly sk = w − ℓ − j + i unused spaces at the end of the k-th line.

Let us fix an integer constant c ≥ 1. We can define the uglyness of each line k as uk = (sk)c. A way of choosing where to break the lines is to minimize the resulting ∑k uk, where the sum is over the indices k of all lines except the last one (we do not care if it has unused space).

Given a text, can you wrap it according to this method?

Input

Input consists of several cases, each one with w, c and n, followed by n words made up of between 1 and w lowercase letters. You can assume 1 ≤ w ≤ 80, 1 ≤ c ≤ 2, and 1 ≤ n ≤ 104.

Output

For every case, print the result of wrapping the text according to the method above. If there are several solutions with minimum total uglyness, choose the one that maximizes the number of words of the first line; in case of a tie, maximize the number of words of the second line, and so on. Print a line with w dashes at the end of each case.

Public test cases
  • Input

    6 1 4
    aaa bb cc ddddd
    
    6 2 4
    aaa bb cc ddddd
    
    6 2 4
    aa bbb cc ddddd
    
    10 2 3
    xxxxx yyyy z
    
    2 1 2
    a a
    
    3 1 2
    a a
    

    Output

    aaa bb
    cc
    ddddd
    ------
    aaa
    bb cc
    ddddd
    ------
    aa bbb
    cc
    ddddd
    ------
    xxxxx yyyy
    z
    ----------
    a
    a
    --
    a a
    ---
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++