QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 256 MB Total points: 100

#3829. 斯蒂芬·库克

Statistics

Stephen Arthur Cook 是一位专门研究复杂性理论等硬核课题的计算机科学家和数学家。他在论文《定理证明过程的复杂性》(The complexity of theorem-proving procedures)中对 P 与 NP 问题给出了精确的陈述,他最著名的贡献之一是证明了布尔可满足性问题(即 SAT)是 NP-hard 的。

Cook 在 1982 年获得了图灵奖。没错,就是那个图灵。如果你不知道我在说什么,请回去看问题 A。因为你也是一个名叫 Cook 的书呆子,所以你挑战了同样书呆子的朋友 Levin,一起玩一个受 Stephen Cook 启发的书呆子游戏。游戏规则如下:你将准备一个布尔公式(实际上我们会为你准备好)。然后,你和 Levin 轮流决定一个变量的值(真或假)。当所有变量的值都确定后,如果公式为真,你就赢了!否则,Levin 赢。那么,作为一个书呆子,你能告诉我如果你先手,你是否能赢得这场游戏吗?当然,假设 Levin 的策略是最优的。

输入格式

输入的第一行包含一个整数 $T$ ($T \le 20$),表示测试用例的数量。每个测试用例包含两行。

第一行包含一个整数 $n$ ($1 \le n \le 10$),表示布尔公式中的变量数量。第 $i$ 个变量用第 $i$ 个大写英文字母表示。也就是说,第一个变量是 A,第三个变量是 C。

对于每个测试用例,第二行给出一个长度不超过 256 个字符的布尔公式。布尔公式必须符合以下五种形式之一:

  • varvar 是一个变量。
  • ( formula1 )formula1 是一个布尔公式。
  • not formula1formula1 是一个布尔公式。
  • formula1 or formula2formula1formula2 均为布尔公式。
  • formula1 and formula2formula1formula2 均为布尔公式。

你可以假设输入文件中变量和运算符之间有空格分隔。布尔运算符有四种:andornot 和括号 ()。注意,前三种运算符均为小写。运算符的优先级从高到低依次为:() > not > and > or

输出格式

输出获胜者的名字(“Cook” 或 “Levin”)。

样例

输入 1

3
1
A and not A
1
A or not A
3
( A or C ) and B

输出 1

Levin
Cook
Cook

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.