小 Z 正在自学量子计算机相关知识,最近他在研究量子通信章节,并遇到了一个有趣的问题。在该问题中,Alice 和 Bob 正在进行量子通信,它们的通信语言是一个大小为 的字典 ,在该字典中,每一个单词 ()都可以用一个 位的 串来表示。在本题中 可以通过调用函数
gen
来生成,选手可以在题目目录下的gen.cpp
中查看,该函数的参数n
、a1
、a2
将由输入数据给出。Alice 和 Bob 接下来要进行 次通信,每次通信由 Alice 向 Bob 传输恰好一个字典中的单词。然而,两人使用的通信信道并不可靠,会受到噪音的干扰。更具体地,对于第 次传输,记 Alice 传输的原单词为 ,该 串会受噪音干扰而翻转最多 位。换句话说,记 Bob 这次收到的 串为 ,它与 相比,可能有最多 位是不同的,并且 可能不在字典 中出现。
与此同时,Bob 得知坏人 Eve 也潜入了两人的通信信道,并准备干扰两人的通信。他的干扰方式是将 Bob 收到的 串变为任意的 位 串,并且这个串可能不在字典 中出现。Eve 非常狡猾,他不一定会对每次通信都进行干扰。
现在 Bob 找来了你帮忙,对于接下来的每次通信,你需要根据 Bob 最终收到的 串以及这次通信的噪音干扰阈值 (),判断这次通信是否有可能没有受到 Eve 的干扰(即 Bob 收到的 串可以由字典中的某个单词翻转至多 位后得到)。本次通信如果有可能没受到 Eve 干扰,请你输出 ,否则输出 。Bob 很信任你的能力,所以你需要在线地回答结果,具体要求见输入格式。
为了降低读入用时, Bob 收到的串将用长度为 的 进制串给出, 进制串中包含数字字符 与大写英文字母 ,其中字符 依次表示数值 。
进制串可以逐位转化为 串,例如:
5
对应0101
,A
对应1010
,C
对应1100
。,,, 和 在 之间均匀随机生成。
观察到由于最多只会翻转 位,所以可以把每个 串都分成 段,这样若没被那个人干扰则总会有一段和字典中的完全一样。
由于数据随机,字典中合法的串的个数大概只有 个,这个数字大概是 ,所以能过。