LibreOJ

2778 「BalticOI 2018」基因工程

内存限制：1024 MB 时间限制：2000 ms

题目描述

题目译自 BalticOI 2018 Day2「Genetics」

给定 $N$ 个长度为 $M$ 的只由 A、T、G 和 C 组成的字符串，分别编号为 $1\ldots N$，其中一个是模式串，其它 $N-1$ 个字符串与模式串都恰好有 $K$ 个字符不同，找到这个模式串。

输入格式

第一行包含三个整数 $N$, $M$ 和 $K$，满足 $1\leqslant K\leqslant M$。

接下来 $N$ 行，每行一个长度为 $M$ 的字符串。

数据保证模式串一定存在。

警告：本题 IO 量较大，对于 Java 或 Python 语言，请使用较为快速的 IO 操作。

输出格式

输出一个整数表示模式串的编号。

样例 1

样例 2

数据范围与提示

子任务 分值 数据范围 附加限制
$1$ $27$ $3\leqslant N,\,M\leqslant 100$
$2$ $19$ $3\leqslant N,\,M\leqslant 1800$ 所有字符串中只包含 A 和 C
$3$ $28$ $3\leqslant N,\,M\leqslant 4100$ 所有字符串中只包含 A 和 C
$4$ $26$ $3\leqslant N,\,M\leqslant 4100$ 　

请注意在 LibreOJ 上共有 $5$ 个子任务，其中第一个子任务为样例。

样例

样例输入 1

4 3 1
ACC
CCA
ACA
AAA

样例输出 1

3

样例输入 2

4 4 3
CATT
CAAA
ATGA
TCTA

样例输出 2

4