You noticed the scam because you were traveling several times by the same place: indeed, you have such a good memory that you can remember very well the path you followed, including each of the loops that your scammer forced you to take.
Now, you are at the police station to file a complaint against this driver and an officer asks you to tell your story. She even asks you to give all the details of the path you took. Because you do not want to lose yet another couple of hours in doing so, you decide to give a compressed version of it.
Suppose you remember you traveled through places A, B, C, D, A, B, C, D. In this case, you prefer telling the officer "I followed twice the path ABCD", rather than "I followed the path ABCDABCD". Given that your path repeated the same sequence of places, this will significantly shorten your statement, without missing any detail.
More precisely, you have to write a program that takes as input the list of places you traveled through, and which returns the size of the shortest compressed form of this path. Such a compressed path can either be:
The input consists of two lines:
Limits
$$$0 < N \le 700$$$.
The output should consist of a single line, whose content is an integer, the size of the shortest compressed path.
22 aaabaaabccdaaabaaabccd
4
4 aaba
3
Sample Explanation 1
The shortest compressed form of the path is $$$(((a)^3 b)^2 (c)^2 d)^2$$$. The atomic paths it contains are $$$a$$$, $$$b$$$, $$$c$$$ and $$$d$$$. Hence, it has size 4.
Sample Explanation 2
The shortest compressed form of the path is $$$(a)^2 ba$$$. The atomic paths it contains are $$$a$$$, $$$b$$$, and $$$a$$$. Hence, it has size 3.
Name |
---|