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 |
