Underscores
Time limit2sMemory limit128 MB
Insert underscores between N given words (counts differing by at most 1) to reach total length M, and output the lexicographically smallest resulting string under a custom character order.
- Level
Medium5 of 10
- Topics
- Greedy, String, Implementation
- Solved
- No attempts yet
Problem
Sejun wants to make a new word of length M by concatenating N given English words in the given order. Between every pair of adjacent words, he must place at least one _.
He may add more _ characters until the new word has length M, but _ may be placed only between words. Therefore, the new word cannot start or end with _.
The number of _ characters between words must be as equal as possible. If all gaps cannot contain the same number, the difference between the maximum and minimum gap counts must be exactly 1.
Print the lexicographically smallest new word that satisfies all conditions.
Input
The first line contains N, the number of words, and M, the required length of the new word. The next N lines each contain one English word.
Output
Print the lexicographically smallest valid new word on one line.
Characters are ordered as follows.
'A' < 'B' < 'C' < ... < 'Z' < '_' < 'a' < 'b' < 'c' < ... < 'z'
Constraints
- 2 <= N <= 10
- 3 <= M <= 200
- Each word consists only of uppercase and lowercase English letters.
- The length of each word is between 1 and 10, inclusive.
- If len is the sum of the lengths of the N words, then len + N - 1 <= M.