#2778. 「BalticOI 2018」基因工程

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Mingqi_H

题目描述

题目译自 BalticOI 2018 Day2「Genetics

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

输入格式

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

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

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

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

输出格式

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

样例

样例 1 输入

4 3 1
ACC
CCA
ACA
AAA

样例 1 输出

3

样例 2 输入

4 4 3
CATT
CAAA
ATGA
TCTA

样例 2 输出

4

数据范围与提示

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

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