0 人解决，2 人已尝试。
0 份提交通过，共有 4 份提交。
9.9 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
Every sequence of small letters a and b (also the empty sequence) is called an ab-word. If X=[x1,..,xn] is an ab-word and i,j are integers such that 1<=i<=j<=n then X[i..j] denotes the subword of X consisting of the letters xi,..,xj. We say that an ab-word X=[x1,..xn] is nice if it has as many letters a as b and for all i=1,…,n the subword X[1,i] has at least as many letters a as b.
Now, we give the inductive definition of the similarity between nice ab-words.
*** Every two empty ab-words (i.e. words with no letters) are similar
*** Two non-empty nice ab-words X=[x1,…,xn] and Y=[y1,..,ym] are similar if they have the same length (n=m) and one of the following conditions if fulfilled:
****1. x1=y1, xn=yn and X[2..n-1] and Y[2..n-1] are similar ab-words and they are both nice;
****2. there exists i, 1<=i<=n, such that X[1..i], X[i+1..n] are nice ab-words and
****a. Y[1..i], Y[i+1..n] are nice ab-words and X[1..i] is similar to Y[1..i] and X[i+1..n] is similar to Y[i+1..n], or
****b. Y[1..n-i], Y[n-i+1..n] are nice ab-words and X[1..i] is similar to Y[n-i+1..n] and X[i+1..n] is similar to Y[1..n-i].
A level of diversity of a non-empty set S of nice ab-words is the maximal number of ab-words that can be chosen from S in such a way that for each pair w1,w2 of chosen words, w1 is not similar to w2.
Write a program that:
1.reads elements of S;
2.computes the level of diversity of the set S
3.writes the result.
In the first line of the input file there is a number n of elements of the set S, 1<=n<=1000; in the following n lines there are elements of the set S, i.e. nice ab-words (one word in each line); the first letter of every ab-word is the first symbol in line and there are no spaces between two consecutive letters in the word; the length of every ab-word is an integer from the range [1..200].
In the first and only line of the text file ABS.OUT there should be written one integer - the level of diversity of S.
3 aabaabbbab abababaabb abaaabbabb
2
0 人解决，2 人已尝试。
0 份提交通过，共有 4 份提交。
9.9 EMB 奖励。