Hide

Problem G
Geneetika

Languages de en et is ja lt lv no pl ru sv

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?

Sisend

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!

Väljund

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

Piirangud

Selles ülesandes on testid jagatud gruppidesse. Iga grupi eest saavad punkte ainult need programmid, mis lahendavad õigesti kõik gruppi kuuluvad testid. Sinu lõplik skoor on esitatud lahenduste skooride maksimum.

Grupp

Punkte

Piirangud

Lisapiirangud

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$

 
Sisendi näide 1 Väljundi näide 1
4 3 1
ACC
CCA
ACA
AAA
3
Sisendi näide 2 Väljundi näide 2
4 4 3
CATT
CAAA
ATGA
TCTA
4