루미 알고리즘

#1276골드Printout

PO 2004 결선코딩출제 Jimmy Mårdell, Håkan Strömberg, Pär Söderhjelm영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Pelle has a text on his computer that he now wants to edit and print. He wants the printout in a “monospaced” font. That is, all characters have the same width (take up the same amount of space on a line). Additionally, he wants to fit the printout to a given line length, n characters per line.

He realizes that it is hardly possible to make every line contain exactly n characters, since there must be exactly one space between two words. However, he is satisfied if he manages to format the printout so that it comes as close to the desired result as possible. As a measure of the result, he defines the deviation in number of characters of the “worst” line from the desired n characters. He now wants to minimize this measure.

Write a program that reads the text and prints it with line breaks at positions such that the above measure is minimized.

Input

The first line of input contains the integer n (5 ≤ n ≤ 80), the desired line length.

The next line contains the integer k (1 ≤ k ≤ 1000), the number of words.

Then follow k lines with one word s (1 ≤ |s| ≤ 20) on each line. The words contain punctuation and the letters a-z and A-Z, but the words themselves cannot contain spaces. Punctuation is treated as part of the word and may not be separated from it. The text you should print consists of these k words in this exact order.

Output

Print the text with line breaks such that the maximum deviation from n is minimized. There must be exactly one space between consecutive words on the same line. If there are several optimal printouts, any one of them will be accepted.

예제

예제 1

입력
30
32
Hej
mor
och
far!
Har
ar
det
varmt
och
skont,
solen
lyser
var
dag
och
det
ar
varmt
i
vattnet!
Just
nu
ligger
jag
pa
stranden
och
laser
en
bok.
Halsningar
Pelle
출력
Hej mor och far! Har ar det varmt
och skont, solen lyser var dag
och det ar varmt i vattnet! Just
nu ligger jag pa stranden och
laser en bok. Halsningar Pelle

출처 표기

출처: Programmeringsolympiaden 2004년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.