{"problem":{"name":"[USACO22DEC] Reverse Engineering B","description":{"content":"Elsie 有一个程序，接受一个 $N(1 \\le N \\le 100)$ 个变量的数组 $b[0], \\cdots ,b[N−1]$ 作为输入，其中每个变量等于 $0$ 或 $1$，并且返回对输入数组应用一系列 `if / else if / else` 语句的结果。每个语句检查至多一个输入变量的值，并返回 $0$ 或 $1$。这类程序的一个例子是： ```cpp if (b[1] == 1)","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8899"},"statements":[{"statement_type":"Markdown","content":"Elsie 有一个程序，接受一个 $N(1 \\le N \\le 100)$ 个变量的数组 $b[0], \\cdots ,b[N−1]$ 作为输入，其中每个变量等于 $0$ 或 $1$，并且返回对输入数组应用一系列 `if / else if / else` 语句的结果。每个语句检查至多一个输入变量的值，并返回 $0$ 或 $1$。这类程序的一个例子是：\n\n```cpp\nif (b[1] == 1) return 1;\nelse if (b[0] == 0) return 0;\nelse return 1;\n```\n\n例如，如果上方程序的输入是 \"10\"（即 $b[0]=1$ 及 $b[1]=0$），那么输出应当为 $1$。 \n\nElsie 告诉了 Bessie 对于 $M(1 \\le M \\le 100)$ 个不同输入的正确输出。Bessie 现在正试图对 Elsie 的程序进行逆向工程。不幸的是，Elsie 可能说了谎；可能不存在上述形式的程序行为与 Elsie 所说的均一致。 \n\n对于 $T(1 \\le T \\le 10)$ 个子测试用例中的每一个，判断 Elsie 是否一定在说谎。\n\n## Input\n\n输入的第一行包含 $T$，为子测试用例的数量。\n\n每一个子测试用例的第一行包含两个整数 $N$ 和 $M$，以下 $M$ 行，每行包含一个由 $N$ 个 $0$ 或 $1$ 组成的字符串，表示一个输入（即 $b[0] \\cdots b[N−1]$ 的值），以及另一个字符（$0$ 或 $1$）表示输出。相邻的子测试用例之间用空行分隔。 \n\n## Output\n\n对于每一个子测试用例，输出一行，包含 $\\texttt{OK}$ 或 $\\texttt{LIE}$，分别表示 Elsie 可能没有说谎或是一定在说谎。 \n\n[samples]\n\n## Note\n\n### 样例 1 解释\n\n以下是第一个子测试用例的一个合法的程序：\n\n```cpp\nif (b[0] == 0) return 0;\nelse return 1;\n```\n\n以下是第一个子测试用例的另一个合法的程序：\n\n```cpp\nif (b[0] == 1) return 1;\nelse return 0;\n```\n\n以下是第二个子测试用例的一个合法的程序：\n\n```cpp\nif (b[1] == 1) return 1;\nelse if (b[0] == 0) return 0;\nelse return 1;\n```\n\n显然，对于第三个子测试用例不存在对应的合法的程序，因为 Elsie 的程序一定始终对相同的输入产生相同的输出。\n\n可以证明对于最后一个子测试用例不存在对应的合法的程序。 \n\n### 测试点性质\n\n- 测试点 $2-3$ 满足 $N=2$。\n- 测试点 $4-5$ 满足 $M=2$。\n- 测试点 $6-12$ 没有额外限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8899","tags":["模拟","贪心","USACO","2022"],"sample_group":[["4\n\n1 3\n0 0\n0 0\n1 1\n\n2 4\n00 0\n01 1\n10 1\n11 1\n\n1 2\n0 1\n0 0\n\n2 4\n00 0\n01 1\n10 1\n11 0","OK\nOK\nLIE\nLIE"]],"created_at":"2026-03-03 11:09:25"}}