经典信息论基于通信信道的概念。
信息论通常被认为是由 Claude Shannon 在 1948 年的开创性著作《通信的数学理论》中创立的。经典信息论的核心范式是噪声信道下的信息传输工程问题。
在本题中,我们将专门考虑最简单的噪声信道之一,即二进制对称信道(BSC)。BSC 传输比特序列,但每个传输的比特都有概率 $p$ 被翻转为错误的比特。这被称为交叉概率,如图所示。我们假设不同比特的行为是独立的,因此传输 $l$ 个比特时,正确传输的概率为 $(1 - p)^l$。注意,我们可以始终假设 $p < 1/2$,因为 $p = 1/2$ 的信道是完全无用的,而 $p > 1/2$ 的信道可以通过翻转输出的所有比特,轻松转换为交叉概率为 $1 - p$ 的新信道。
当然,在噪声信道上进行通信仍然是可能的。(事实上,你一直在这样做!)为了做到这一点,必须添加额外的比特,以便接收方检测甚至纠正错误。这种特性的示例实现包括奇偶校验位、循环冗余校验(CRC)和 Golay 码。然而,这些与本题无关,因此在此不做讨论。
在本题中,你必须研究二进制对称信道的行为。
输入格式
输入的第一行包含一个整数 $T$,表示传输次数。 接下来有 $T$ 行,每行包含一次传输的输入和输出,均为二进制字符串,中间由一个空格分隔。
输出格式
对于每次传输,如果通信传输正确,输出 OK,否则输出 ERROR。
数据范围
- $0 < T \leq 100$
- 所有输入和输出的长度均小于 $120$。
- $T$ 以十进制编码。
样例
输入格式 1
2 10 10 10 11
输出格式 1
OK ERROR