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