https://codeforces.com/problemset/problem/803/D
D. Magazine Ad
time limit per test
1 second
memory limit per test
256 megabytes
The main city magazine offers its readers an opportunity to publish their ads. The format of the ad should be like this:
There are space-separated non-empty words of lowercase and uppercase Latin letters.
There are hyphen characters '-' in some words, their positions set word wrapping points. Word can include more than one hyphen.
It is guaranteed that there are no adjacent spaces and no adjacent hyphens. No hyphen is adjacent to space. There are no spaces and no hyphens before the first word and after the last word.
When the word is wrapped, the part of the word before hyphen and the hyphen itself stay on current line and the next part of the word is put on the next line. You can also put line break between two words, in that case the space stays on current line. Check notes for better understanding.
The ad can occupy no more that k lines and should have minimal width. The width of the ad is the maximal length of string (letters, spaces and hyphens are counted) in it.
You should write a program that will find minimal width of the ad.
Output
Output minimal width of the ad.
Note
Here all spaces are replaced with dots.
In the first example one of possible results after all word wraps looks like this:
garage.
for.
sa-
le
The second example:
Edu-ca-
tion-al.
Ro-unds.
are.so.fun
《主要城市》杂志为读者提供了刊登广告的机会。广告的格式应该是这样的：
有小写和大写拉丁字母的空格分隔的非空单词。
有些单词中有连字符“-”，它们的位置设置单词换行点。单词可以包含多个连字符。
保证没有相邻的空格和连字符。空格旁边没有连字符。在第一个单词之前和最后一个单词之后没有空格和连字符。
当单词被换行时，连字符之前的单词部分和连字符本身保留在当前行上，单词的下一部分放在下一行上。您还可以在两个单词之间放置换行符，在这种情况下，空格将保留在当前行上。检查注释以更好地理解。
广告不能占用超过k行，并且应该具有最小的宽度。广告的宽度是其中字符串的最大长度（包括字母、空格和连字符）。
你应该编写一个程序，找出广告的最小宽度。