|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
C - Jukebox
Languages: C, C++, Java, Haskell, Pascal, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
The ICPC judges are preparing a party for the opening ceremony. For the party, they intend to add a playlist with some songs to the jukebox software (a simple MP3 player). However, there are so many songs in the computer that it is difficult to find the ones they want to add. As a consequence, they need to use the search feature many times.
In this jukebox, when you search for a string s, the software returns every music whose title or artist name contains s as a substring. String $s$ is a substring of string $t$ if $t$ contains all characters of $s$ as a contiguous sequence (for example, $\texttt{‘bc’}$ is a substring of $\texttt{‘abcd’}$, but $\texttt{‘ac’}$ is not). To save their precious time, while looking for a song, they always use one of the song’s golden string, i.e. one of the shortest strings for which the search returns as a result only the song they want.
In the example above, a possible golden string for the song $\texttt{‘johnnatan’}$ is $\texttt{‘ta’}$. Note that $\texttt{‘ta’}$ is not a substring of the name of another song nor a substring of the artist of another song. Note also that there is no string of size equal to $1$ that could identify uniquely the song $\texttt{‘johnnatan’}$.
They discovered that if they remove the artist fields from some of the songs they can get even smaller golden strings. For the song $\texttt{‘john’}$, there is no golden string. However, if one removes the artist field from all other songs, the string $\texttt{‘c’}$ becomes the golden string for the song $\texttt{‘john’}$.
Given the song list (each song with name and artist), your job is to determine the minimum sum of the golden string sizes for all songs that can be obtained if one is allowed to remove some of the artist fields. In the figure above you can see a possible best result with the golden strings in bold. The minimum sum of the golden string sizes in this case is $10$.
Input
The input contains several test cases. The first line of each test case contains one integer $N$ $(1 \leq N \leq 30)$, which indicates the number of songs. Following there will be $N$ pairs of lines ($2 \times N$ lines), one pair for each song. The first line of a pair will contain the song name, the second line will contain the artist name. Both artist and song names are strings containing only lower case letters or underlines and having at least $1$ and at most $30$ characters. There will be at most $6$ different artists in the list. The end of the input is given by $N = 0$.
The input must be read from standard input.
Output
For each test case your program must output one single line with the minimum sum of the golden string sizes. You may assume that there will always be a solution.
The output must be written to standard output.
Sample test(s)
Input
8
a_flor
los_hermanos
anna_julia
los_hermanos
quem_sabe
los_hermanos
pierrot
los_hermanos
azedume
los_hermanos
johnny
massacration
johnnatan
massacration
john
massacration
4
c
axc
b
axc
d
cc
xc
cc
0
Output
10
5