Baltic OI '18 P5 - Genetics

View as PDF

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
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 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 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 places compared to the real villain's.

Can you identify the real villain?

Input

The first line contains the three integers , , and , where . The following lines represent the DNA sequences. Each of these lines consists of 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 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 None
2 19 All characters are either A or C.
3 28 All characters are either A or C.
4 26 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

Comments

There are no comments at the moment.