Problem G
Genetics
Languages
de
en
et
is
ja
lt
lv
no
pl
ru
sv
For villains that intend to take over the world, a common way to avoid getting caught is to clone themselves. You have managed to catch an evil villain and her $N-1$ clones, and you are now trying to figure out which one of them is the real villain.
To your aid you have each person’s DNA sequence, consisting of $M$ characters, each being either A, C, G or T. You also know that the clones are not perfectly made; rather, their sequences differ in exactly $K$ places compared to the real villain’s.
Can you identify the real villain?
Input
The first line contains the three integers $N$, $M$, and $K$, where $1 \le K \le M$. The following $N$ lines represent the DNA sequences. Each of these lines consists of $M$ characters, each of which is either A, C, G or T.
In the input, there is exactly one sequence that differs from all the other sequences in exactly $K$ places.
Warning: this problem has rather large amounts of input, and will require fast IO in Java.
Output
Output an integer – the index of the DNA sequence that belongs to the villain. The sequences are numbered starting from $1$.
Constraints
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.
|
Group |
Points |
Limits |
Additional Constraints |
|
1 |
27 |
$3 \le N, M \le 100$ |
|
|
2 |
19 |
$3 \le N, M \le 1800$ |
All characters are either A or C. |
|
3 |
28 |
$3 \le N, M \le 4100$ |
All characters are either A or C. |
|
4 |
26 |
$3 \le N, M \le 4100$ |
| Sample Input 1 | Sample Output 1 |
|---|---|
4 3 1 ACC CCA ACA AAA |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 4 3 CATT CAAA ATGA TCTA |
4 |
