CF566A Matching Names

Teachers of one programming summer school decided to make a surprise for the students by giving them names in the style of the "Hobbit" movie. Each student must get a pseudonym maximally similar to his own name. The pseudonym must be a name of some character of the popular saga and now the teachers are busy matching pseudonyms to student names. There are $ n $ students in a summer school. Teachers chose exactly $ n $ pseudonyms for them. Each student must get exactly one pseudonym corresponding to him. Let us determine the relevance of a pseudonym $ b $ to a student with name $ a $ as the length of the largest common prefix $ a $ and $ b $ . We will represent such value as . Then we can determine the quality of matching of the pseudonyms to students as a sum of relevances of all pseudonyms to the corresponding students. Find the matching between students and pseudonyms with the maximum quality.

N/A

N/A

The first test from the statement the match looks as follows: - bill $ → $ bilbo (lcp = 3) - galya $ → $ galadriel (lcp = 3) - gennady $ → $ gendalf (lcp = 3) - toshik $ → $ torin (lcp = 2) - boris $ → $ smaug (lcp = 0)