Problem F
Генетика
Languages
de
en
et
is
ja
lt
lv
no
pl
ru
sv
Клонирование себя – способ маскировки, которым часто пользуются ужасные злодеи, собирающиеся захватить вселенную. Вы недавно захватили ужасного злодея вместе с его $N-1$ клонами, и пытаетесь узнать, кто же из них всех является оригинальным злодеем, а кто – клоны.
К счастью, у вас есть доступ к последовательностям ДНК всех подозреваемых. Каждая последовательность состоит из $M$ символов A, C, G или T. Известно, что клоны сделаны неидеально – их ДНК отличается от оригинала ровно в $K$ позициях.
Можете ли вы распознать настоящего злодея?
Ввод
На первой строке даны три целых числа $N$, $M$, и $K$, где $1 \le K \le M$. На следующих $N$ строках даны последовательности ДНК. Каждая из них состоит из $M$ символов A, C, G или T.
Только одна из данных в файле последовательностей отличается от каждой из остальных ровно в $K$ позициях.
Внимание: объем входных данных в этой задаче довольно большой и требует использования быстрых библиотек ввода-вывода в Java.
Вывод
Выведите целое число – номер ДНК последовательности настоящего злодея. Последовательности нумеруются с $1$.
Ограничения
Тесты разделены на группы. Очки за группу даются только если корректно решены все тесты в группе.
|
Группа |
Очки |
Ограничения |
Дополнительные ограничения |
|
1 |
27 |
$3 \le N, M \le 100$ |
|
|
2 |
19 |
$3 \le N, M \le 1800$ |
Только символы A и C. |
|
3 |
28 |
$3 \le N, M \le 4100$ |
Только символы A и C. |
|
4 |
26 |
$3 \le N, M \le 4100$ |
| Пример ввода 1 | Пример вывода 1 |
|---|---|
4 3 1 ACC CCA ACA AAA |
3 |
| Пример ввода 2 | Пример вывода 2 |
|---|---|
4 4 3 CATT CAAA ATGA TCTA |
4 |
