ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2012

About     Problems     Submit solution     Judge status     Standings
Contest is over

I. Brute-force Search

Time limit: 1.0 second
Memory limit: 64 MB
Space tourism has gained unprecedented popularity in recent years. There are lots of people wishing to look closely at a triple star, walk on the surface of a small asteroid or plunge into the depths of a gas giant. Passenger ships began to fly between all popular star sectors. But there is a little problem—a flight to a place of interest may take several weeks, and you need to escape the boredom somehow, because even a view out of the observation window doesn't change very often. That's why many people now take a great interest in reading visual novels.
A visual novel is one of the attempts to rethink the conventional literature which became possible after the mass transfer of books to electronic devices. The main difference of the visual novel from an usual book is that its plot can branch out, and after a few pages the reader may have more than one option of choosing which page is next. The moments when the reader has to make choices are called branches.
Many readers like to explore the entire novel, reading all possible scenarios. After reaching one of the possible endings, they return to the beginning of the story and try other plot variants. You, as the author of the novel “The song of Asya”, want to make life of such readers easier. First, after reading several endings the reader forgets for what choices he has already explored all possible ways of further plot development. So you have decided that the story should not offer options which lead the reader to the fully explored chains of events. Secondly, you have decided to add a button, which skips all the intermediate pages of a story to the nearest branch or the finale. If you accidentally press this button on a branch page, then nothing happens.
You have written all the chains of choices, leading to all the possible endings, and you want to assess the total number of button clicks needed to choose the plot lines and skip the unambiguous choices, which the reader needs in the best case to read the entire novel in all its versions.


The first line contains an integer n that is an amount of different endings of the story (1 ≤ n ≤ 105). The i'th from the following n lines contains a non-empty line of lowercase Latin letters, describing all choices of the plot on the way to the i'th ending. It is guaranteed that none of the lines is a prefix of the other line. The total length of lines does not exceed 105.


Output the minimum amount of button clicks necessary to read all the possible variants of the plot.




If we denote the choice button clicks with Latin letters, and the skip branch button clicks with the “*” symbol, then one of the optimal strategies is “b*c*”.
Problem Author: Denis Dublennykh (prepared by Alexander Fetisov)
Problem Source: Ural Championship 2012
To submit the solution for this problem go to the Problem set: 1908. Brute-force Search