Baltic Olympiad in Informatics 2018 Open - day 2

Start

2018-04-29 09:30 CEST

Baltic Olympiad in Informatics 2018 Open - day 2

End

2018-04-29 14:30 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -570 days 15:36:21

Time elapsed

5:00:00

Time remaining

0:00:00

Problem B
Ģenētika

Priekš ļaundarēm, kas vēlas pārņemt pasauli, ierasts veids izvairīties no notveršanas ir sevis klonēšana. Jums izdevās noķert kādu ļaundari un viņas $N-1$ klonus, un tagad jūs mēģinat saprast, kura no tām ir īstā ļaundare.

Jūsu rīcībā ir katras personas DNS virkne, kas sastāv no $M$ simboliem, katrs no kuriem ir A, C, G vai T. Jūs arī zinat, ka kloni nav ideāli veidoti; precīzāk, viņu DNS virknes atšķiras tieši $K$ vietās, salīdzinot ar īstās ļaundares virkni.

Vai jūs varat atpazīt īsto ļaundari?

Ievaddati

Pirmā rinda satur trīs veselu skaitļus $N$, $M$ un $K$, kur $1 \le K \le M$. Sekojošas $N$ rindas apraksta DNS virknes. Katra no šīm rindām satur $M$ simbolus; katrs no tiem ir A, C, G vai T.

Starp ievada virknēm pastāv tieši viena, kas atšķiras no visām pārējām precīzi $K$ vietās.

Brīdinājums: šim uzdevumam ir diezgan lieli ievaddati, kas prasīs ātru ievadu/izvadu valodā Java.

Izvaddati

Izvadiet veselu skaitli — īstās ļaundares DNS virknes numuru. Virkņu numerācija sākas ar $1$.

Ierobežojumi

Jūsu risinājums tiks testēts uz vairākām testu grupām, par katru no tām var iegūt punktus. Katra testu grupa satur vienu vai vairākus testus. Lai iegūtu punktus par testu grupu, jums ir pareizi jāatrisina visi testi šajā grupā. Jūsu beigu vērtējums par uzdevumu būs starp visiem iesūtījumiem lielākais.

Grupa

Punkti

Ierobežojumi

Papildu ierobežojumi

1

27

$3 \le N, M \le 100$

 

2

19

$3 \le N, M \le 1800$

Visi simboli ir A vai C.

3

28

$3 \le N, M \le 4100$

Visi simboli ir A vai C.

4

26

$3 \le N, M \le 4100$

 
Ievaddatu paraugs 1 Izvaddatu paraugs 1
4 3 1
ACC
CCA
ACA
AAA
3
Ievaddatu paraugs 2 Izvaddatu paraugs 2
4 4 3
CATT
CAAA
ATGA
TCTA
4