Problem D
Hyphenland
In a distant country called Hyphen-Land, a benevolent
dictator made a rule stating that upon marriage every pair of
people must hyphenate their names to make them identical by
last-name. This was lauded both as a symbol of equality among
spouses, and also a great way to manage people’s identities and
track lineages. As a result, the children of each set of
parents will have both their parents’ last names, hyphenated in
alphabetical order. This pattern is to continue over every
generation. For the case of this question, keep in mind that
each ’name’ that is mentioned refers to a last name that exists
within hyphens when applicable.
For example, if two individuals marry and their last names are
”Smith” and ”Doe” respectively, their resulting last name is
”Smith-Doe”.
Speaking of managing people’s identities, this nation’s
national register of citizens now has a different problem.
While earlier their problem became of keep track of names and
identities, now they have no idea how to even contain these
names in their databases. For every citizen’s profile
information, only a finite amount of computer memory can be
used for the name of a specific person, which involves the a
first name and a last name. For this question, we only care
about last names.
The solution that Hyphen-Land’s engineers came up with was to
reduce the length of each last name. So, as we add more and
more last names, we must remove the ends of older last names.
Keep in mind that the hyphens themselves don’t consume any
data, so don’t count them in your name-size. Future last names
may have hyphens in them too, but don’t count them either.
You are likely to have ties in your effort to shorten names.
Here is the order in which you should break the ties:
-
Reduce the longest portion first.
-
If tied in length, reduce all the longest ones, starting from the first names in the string.
-
If all are tied, then start removing letters from first names in the longer string.
Input
The input is described as follows: Line $1$: Two integers $t$ and $u$, indicating the total number of lines in the input and number of upgrades ($4 \le t \le 10\, 000$ and $1 \le u \le 100$). Line $2$: The first name. Line $3$: Two integers $g1$ and $n1$, indicating the maximum size (in number of letters) of each name and the number of following names for each generation. Assume no remarriages (for the sake of simplifying the problem) and that we are working with immediate descendants only. Line $4$: One name for each generation. Line $4$ + $n1$: Two integers $g2$ and $n2$ indicating the new size of names and the number of generations of names as before. The above pattern shown from line $4$ to $4$ + $n1$ repeats $u$ times. Keep in mind that hyphens don’t consume any space, so don’t count them in any size-calculations you make, but don’t forget to include them in the output.
Output
The output should be a single last name appropriately hyphenated. When reducing the size of each name, keep in mind to not forget the hyphens, and modify the length and size of each name within each last name appropriately, but keep at least one letter of each name no matter what.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 1 Smith 10 1 Doe |
Smith-Doe |
| Sample Input 2 | Sample Output 2 |
|---|---|
7 2 Smith 10 2 Doe Bruce-Lee 20 1 Cho-Chang |
Sm-Do-Bru-Lee-Cho-Chang |
