Ispit
레이팅 미적용의견: 0
2 \(s / 64\) \(MB / 90\) points
After 26 years of studying, little Mirko took his potentially last exam. He confidently took his seat,
sharpened his pencil and waited calmly for the professor's permission to start writing – after all, that
was his favorite subject, Data Structures and Algorithms . But, as in any good story, this one also has
that but ... Namely, when he got his exam, Mirko could not even comprehend what was written in it.
He only saw a meaningless matrix of letters with \(N\) rows and \(N\) columns.
Since the professor forbid leaving the classroom during the exam, Mirko decided to spend 2 hours
coming up with his own task. Mirko was wondering if it is possible to select \(K\) consecutive columns of
the matrix so that, after arbitrarily shuffling letters in the \(K\) selected columns’ rows, there are two
equal rows of the matrix. Shuffling is allowed only inside of the same row within selected columns
and it is possible that a row remains unchanged after such operation.
Can you solve Mirko's task?
In the test samples totally worth 30% of the points it will hold \(N\) ≤ 10.
In the test samples totally worth additional 40% of the points it will hold \(N\) ≤ 200.
In the first line of the input there are two integer numbers \(N\) and \(K\) (2 ≤ \(K\) ≤ \(N\) ≤ 500).
The following \(N\) rows contain \(N\) lowercase letters of the english alphabet describing the matrix of the
letters Mirko saw in the exam.
Print “DA” (Croatian for yes, without the quotation marks) if it is possible to select the \(K\) consecutive
columns that meet the conditions of the task. Otherwise print “NE” (Croatian for no, also without
quotation marks).
4 2
abcd
acbd
enaa
moze
2 2
aa
aa
3 2
nec
uuc
itioutput
output
DA
DA
NE
2 s / 64 MB / 90 pointsExplanation of the first test sample:
E.g. we can choose columns 2 and 3 and change the matrix so that it looks like this (we can choose not to
change the first row and swap 2 nd and 3 rd letters in other rows):
abcd
abcd
eana
mzoe
It is clear that the first and the second row are the same, thus satisfying the task condition.
평가 및 의견
Ispit
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Ispit