#532. Reverse Engineering B

Reverse Engineering B

题目描述

Elsie 有一个程序,接受一个 N(1N100)N(1 \le N \le 100) 个变量的数组 b[0],,b[N1]b[0], \cdots ,b[N−1] 作为输入,其中每个变量等于 0011,并且返回对输入数组应用一系列 if / else if / else 语句的结果。每个语句检查至多一个输入变量的值,并返回 0011。这类程序的一个例子是:

if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;

例如,如果上方程序的输入是 "10"(即 b[0]=1b[0]=1b[1]=0b[1]=0),那么输出应当为 11

Elsie 告诉了 Bessie 对于 M(1M100)M(1 \le M \le 100) 个不同输入的正确输出。Bessie 现在正试图对 Elsie 的程序进行逆向工程。不幸的是,Elsie 可能说了谎;可能不存在上述形式的程序行为与 Elsie 所说的均一致。

对于 T(1T10)T(1 \le T \le 10) 个子测试用例中的每一个,判断 Elsie 是否一定在说谎。

输入格式

输入的第一行包含 TT,为子测试用例的数量。

每一个子测试用例的第一行包含两个整数 NNMM,以下 MM 行,每行包含一个由 NN0011 组成的字符串,表示一个输入(即 b[0]b[N1]b[0] \cdots b[N−1] 的值),以及另一个字符(0011)表示输出。相邻的子测试用例之间用空行分隔。

输出格式

对于每一个子测试用例,输出一行,包含 OK\texttt{OK}LIE\texttt{LIE},分别表示 Elsie 可能没有说谎或是一定在说谎。

4

1 3
0 0
0 0
1 1

2 4
00 0
01 1
10 1
11 1

1 2
0 1
0 0

2 4
00 0
01 1
10 1
11 0
OK
OK
LIE
LIE

提示

样例解释

以下是第一个子测试用例的一个合法的程序:

if (b[0] == 0) return 0;
else return 1;

以下是第一个子测试用例的另一个合法的程序:

if (b[0] == 1) return 1;
else return 0;

以下是第二个子测试用例的一个合法的程序:

if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;

显然,对于第三个子测试用例不存在对应的合法的程序,因为 Elsie 的程序一定始终对相同的输入产生相同的输出。

可以证明对于最后一个子测试用例不存在对应的合法的程序。

测试点性质

  • 测试点 232-3 满足 N=2N=2
  • 测试点 454-5 满足 M=2M=2
  • 测试点 6126-12 没有额外限制。