Hide

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