Savez
레이팅 미적용의견: 0
\(2^{th}\) round, November \(7^{th}\) 2015
1 sekunda, 64 MB, 120 bodova
There are eight planets and one planetoid in the Solar system. It is not a well known fact that there is
a secret planet S4 inhabited by small creatures similar to bears, their codename being Lodas. Although
this fact is well hidden from the public, the association Savez sent a team lead by general Henrik to
study the Lodas. It has been discovered that Lodas have the ability of teleportation and he wants to
hire them in his army.
One Lod consists of \(N\) strings where the \(i\)th string is denoted by \(x_{i}\). Research has shown that the
number of teleportations a Loda can make depends on one special subsequence (not necessarily
consecutive) of these strings. Strings \(x@@RISE_MATH_BLOCK_0@@j\) (\(i < j\)) can both be in that sequence if and only if
string \(x@@RISE_MATH_BLOCK_1@@i\). The number of teleportations a Loda can make
is the length of the longest described subsequence.
Determine the number of teleportations.
In test cases worth 40% of total points, it will hold (1 ⩽\(N\) ⩽500).
The first line of input contains of the integer \(N\), the number of strings. Each of the following N lines
contains one string consisting of uppercase letters of the English alphabet. The input data will be such
that there will be less than two million characters in total.
The first and only line of output must contain the number of teleportations a Loda can make.
5
A
B
AA
BBB
AAA
5
A
ABA
BBB
ABABA
AAAAAB
6
A
B
A
B
A
Boutput
output
3
3
3Clarification of the first example: Prefix and suffix can intersect so subsequence is A →AA →AAA
Clarification of the third example: Strings in the subsequence are allowed to be equal so subsequence is
A →A →A or B →B →B
평가 및 의견
Savez
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Savez