Baltic Olympiad in Informatics: 2018 Day 2, Problem 2
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
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?
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
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 an integer – the index of the DNA sequence that belongs to the villain. The sequences are numbered starting from 1.
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.
|1||27||~3 \le N, M \le 100~||None|
|2||19||~3 \le N, M \le 1800~||All characters are either |
|3||28||~3 \le N, M \le 4100~||All characters are either |
|4||26||~3 \le N, M \le 4100~||None|
Sample Input 1
4 3 1 ACC CCA ACA AAA
Sample Output 1
Sample Input 2
4 4 3 CATT CAAA ATGA TCTA
Sample Output 2