#P5890. 「BalticOI 2018」基因工程

    ID: 4891 传统题 1500ms 888MiB 尝试: 4 已通过: 2 难度: 7 上传者: 标签>难度分类提高+/省选-随机化与近似随机赋权检测构造与建模交换求和顺序CF2200

「BalticOI 2018」基因工程

题目描述

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

输入格式

第一行包含三个整数 NN, MM 和 KK,满足 1⩽K⩽M1\leqslant K\leqslant M。

接下来 NN 行,每行一个长度为 MM 的字符串。

保证恰好有一个字符串,与其他每个字符串都恰在 KK 个位置上不同。

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

输出格式

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

样例 #1

样例输入 #1

4 3 1
ACC
CCA
ACA
AAA

样例输出 #1

3

样例 #2

样例输入 #2

4 4 3
CATT
CAAA
ATGA
TCTA

样例输出 #2

4

数据范围与提示

子任务 分值 数据范围 附加限制
11 2727 3⩽N, M⩽1003\leqslant N,\,M\leqslant 100
22 1919 3⩽N, M⩽18003\leqslant N,\,M\leqslant 1800 所有字符串中只包含 A 和 C
33 2828 3⩽N, M⩽41003\leqslant N,\,M\leqslant 4100
44 2626