Baltic Olympiad in Informatics 2018 Open - day 2

Start

2018-04-29 07:30 UTC

Baltic Olympiad in Informatics 2018 Open - day 2

End

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

Time elapsed

5:00:00

Time remaining

0:00:00

Problem B
Geneetika

Superkurjategijatel on tavaliseks pääsemise viisiks kloonida endast palju koopiaid. Sul on õnnestunud kätte saada üks selline superkurjategija ja tema $N-1$ klooni, aga nüüd tuleb sul kindlaks teha, kes neist on originaal.

Et sind selles aidata, on sul iga isiku DNA järjend, mis koosneb $M$ märgist, millest igaüks on kas A, C, G või T. On ka teada, et kloonid ei ole perfektsed, vaid nende järjendid erinevad originaalist täpselt $K$ märgi osas.

Kas sa suudad leida õige kurjategija?

Input

Sisendi esimesel real on kolm täisarvu $N$, $M$ ja $K$, kus $1 \le K \le M$. Järgmistel $N$ real on DNA järjendid. Igal real on $M$ märki, mis on kõik kas A, C, G või T.

Täpselt üks sisendis toodud järjenditest on selline, mis erineb kõigist teistest täpselt $K$ märgi osas.

Pane tähele, et siin ülesandes võib olla suuri sisendandmeid!

Output

Väljastada üks täisarv: esialgsele kurjategijale kuuluva DNA järjendi indeks. Järjendite nummerdamine algab $1$-st.

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$

Kõik märgid on kas A või C.

3

28

$3 \le N, M \le 4100$

Kõik märgid on kas A või 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