← 返回题目列表

Codeforces · 217/C

C. 福尔莫罗萨

中文机器翻译题面 查看原题

Bytelandian 生物研究所 (BIBR) 正在研究两种细菌的​​特性,简称为 0 和 1。即使在显微镜下,这两种细菌也很难区分。事实上,科学家们唯一能够区分它们的就是一种叫做福尔摩罗莎的植物。

如果科学家们将细菌菌落样本放置在福穆罗莎叶子上,它将激活一个复杂的营养过程。在此过程中,Formurosa 的颜色会发生变化,以反映细菌种类的逻辑公式(可能非常复杂)的结果,其中涉及常数和运算符 | (或)、& (与) 和 ^ (异或)。如果它是0,植物就会变成红色,否则——它就会变成蓝色。

例如,福尔摩沙的营养过程用公式描述:(((?^?)|?)&(1^?));那么福尔摩沙有四片叶子(“?”符号表示叶子)。如果我们将 0, 1, 0, 0 放在各个叶子上,营养过程的结果将是 (((0^1)|0)&(1^0)) = 1,因此植物会变成蓝色。

科学家们有n个细菌菌落。他们不知道自己的类型;他们唯一确定的是,并非所有的殖民地都是同一类型。他们希望通过与福尔莫罗萨公司的反复评估来尝试确定细菌的种类。在每次评估期间,他们必须在植物的每一片叶子上放置一个样品。然而,他们可能在一次评估中使用一个菌落的多个样本;它们甚至可以用一个菌落的细菌覆盖整个植物!

他们是否有可能始终确定每个群体的物种,无论它们是什么(假设它们并不完全相同)?

输入

输入的第一行包含一个整数 n (2 ≤ n ≤ 106) — 细菌菌落数。

第二行包含描述福尔摩罗莎营养过程的配方。该行仅包含字符 «0», «1», «?», «|», «&», «^», «(», «)» 并符合以下语法:

s → 0|1|?|(s|s)|(s&s)|(s^s)

公式长度不超过 106 个字符。

输出

如果始终可以确定每个菌落的物种,则输出“YES”(不带引号)。否则,输出“NO”(不带引号)。

示例

输入 #1

2
(?^?)

输出 #1

NO

输入 #2

10
?

输出 #2

YES

输入 #3

2
((?^?)&?)

输出 #3

YES