Baltic OI '18 P5 - Genetics

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem type
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 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 None
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 None

Sample Input 1

4 3 1
ACC
CCA
ACA
AAA

Sample Output 1

3

Sample Input 2

4 4 3
CATT
CAAA
ATGA
TCTA

Sample Output 2

4
Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

There are no comments at the moment.