Problem G
Genetika
Languages
de
en
et
is
ja
lt
lv
no
pl
ru
sv
Piktadariai, norintys užvaldyti pasaulį, klonuoja save – taip sunkiau pagauti tikrąjį piktadarį. Jums pavyko pagauti tokią piktadarę ir jos $N-1$ klonų, ir dabar bandote nustatyti, kuri iš jų yra tikroji piktadarė.
Žinoma kiekvienos jų DNR seka, kurią sudaro $M$ raidžių, kiekviena kurių yra A, C, G arba T. Kadangi klonavimo procesas netobulas, kiekvieno klono DNR seka nuo tikrosios piktadarės DNR sekos skiriasi lygiai $K$ pozicijų.
Ar galite rasti tikrąją piktadarę?
Pradiniai duomenys
Pirmoje eilutėje pateikti trys sveikieji skaičiai $N$, $M$ ir $K$, $1 \le K \le M$. Tolesnės $N$ eilučių nusako DNR sekas. Kiekvienoje jų bus po $M$ simbolių, kiekvienas jų bus A, C, G arba T.
Tarp pateiktų yra lygiai viena seka, kuri nuo visų kitų skiriasi lygiai $K$ pozicijų.
Pastaba: šiame uždavinyje didelis kiekis pradinių duomenų gali reikalauti greito įvedimo/išvedimo programuojant Java kalba.
Rezultatai
Išveskite vieną skaičių – DNR sekos, priklausančios tikrajai piktadarei, numerį. Sekos numeruojamos pradedant nuo $1$.
Ribojimai
Jūsų sprendimas bus testuojamas su keliomis testų grupėmis, kiekviena kurių vertinama tam tikru skaičiumi taškų. Kiekvieną testų grupę sudarys keletas testų. Taškai už testų grupę skiriami tik jei įveikiate visus tos grupės testus.
|
Grupė |
Taškai |
Ribojimai |
Papildomi ribojimai |
|
1 |
27 |
$3 \le N, M \le 100$ |
|
|
2 |
19 |
$3 \le N, M \le 1800$ |
Visi simboliai yra A arba C. |
|
3 |
28 |
$3 \le N, M \le 4100$ |
Visi simboliai yra A arba C. |
|
4 |
26 |
$3 \le N, M \le 4100$ |
| Pradiniai duomenys 1 | Rezultatai 1 |
|---|---|
4 3 1 ACC CCA ACA AAA |
3 |
| Pradiniai duomenys 2 | Rezultatai 2 |
|---|---|
4 4 3 CATT CAAA ATGA TCTA |
4 |
