Problem F
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?
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 |
