Baltic Olympiad in Informatics 2018 Open - day 2

Start

2018-04-29 09:30 CEST

Baltic Olympiad in Informatics 2018 Open - day 2

End

2018-04-29 14:30 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -570 days 14:51:12

Time elapsed

5:00:00

Time remaining

0:00:00

Problem B
Genetik

Vissa förbrytare vill ta över världen. Ett vanligt sätt för förbrytare att undvika att bli straffade är att klona sig själva. Du har nu fångat en förbrytare och hennes $N-1$ kloner. Du ska ta reda på vem av dem som är den riktiga förbrytaren.

Du har tillgång till varje infångad persons DNA, som består av $M$ bokstäver där varje bokstav är antingen A, C, G eller T. Du vet också att klonerna inte är perfekta kopior, utan DNA-sekvensen för varje klon skiljer sig på exakt $K$ ställen jämfört med den riktiga förbrytaren.

Kan du identifiera den riktiga förbrytaren?

Input

Den första raden innehåller tre heltal $N$, $M$ och $K$, där $1 \le K \le M$. Följande $N$ rader innehåller DNA-sekvenser. Varje av dessa innehåller $M$ bokstäver, där varje bokstav är någon av A, C, G or T.

Det finns, i inputen, exakt en sekvens som skiljer sig från alla andra på exakt $K$ ställen.

Varning: Det här problemet har stora mängder indata, och kräver snabb IO om man använder Java.

Output

Skriv ut ett heltal – indexet av DNA-sekvensen som tillhör förbrytaren. Sekvensernas index börjar med $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$

Alla bokstäver är antingen A eller C.

3

28

$3 \le N, M \le 4100$

Alla bokstäver är antingen A eller 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