[NFLSPC #6] 真理祭坛

题目背景

天色已晚,围观的人群散得差不多了。人们可能都没有注意到,还有一个瘦小的身影在向真理祭坛跑去。 「你是哪个领域的科学家?怎么就你一个人?」排险者歪了歪头,看着眼前的小 Y 问道。 「我不是科学家。我只是一个高中生。」 「学生?」排险者很困惑,「那你想问什么?」 「我想知道宇宙的终极规律。」 「既然你只是个学生,你认为我该如何让你理解宇宙的规律呢?」 「啊?」小 Y 似乎感到很惊讶,片刻之后,他的脸上出现了些许失望的神情。「宇宙的真理不应该简洁到每个人都能理解吗……难道不是吗?」 「真理可没这么简单。且不说宇宙,我在此随意给你一些『道理』,你能用简洁的语言描述它吗?」 小 Y 抬起头来,看着排险者用全息投影显示在天空中的几串密密麻麻的零和一,陷入了沉思。

题目描述

有 $n$ 个 **命题变项**,记作 $P_0, P_1, \cdots, P_{n - 1}$,其 **真值** 是一个布尔值,要么为 $0$ 要么为 $1$。 我们称一个 **道理** 是一个输入 $n$ 个布尔值、输出一个布尔值的函数,即一个 $\{0, 1\}^n \to \{0, 1\}$ 的映射。 满足特定条件的字符串称为 **合式公式**(Well-Formed Formula,WFF),每个合式公式都对应着唯一一个道理,称为该公式的 **真值表**。具体地: - 一个命题变项 $P_i$ 是合式公式,它的真值表总是输出其所接受的第 $i$ 个输入值($n$ 个输入值的编号依次为 $0, 1, \cdots, n - 1$)。 - 如果 $k$ 个字符串 $A_1, A_2, \cdots, A_k$($k \geq 1$)都是合式公式,则 $(A_1 \land A_2 \land \cdots \land A_k)$ 也是合式公式,它的真值表在接受输入 $I$ 时输出的值为 $A_1, A_2, \cdots, A_k$ 分别的真值表接受 $I$ 时输出的值的最小值。 - 如果 $k$ 个字符串 $A_1, A_2, \cdots, A_k$($k \geq 1$)都是合式公式,则 $(A_1 \lor A_2 \lor \cdots \lor A_k)$ 也是合式公式,它的真值表在接受输入 $I$ 时输出的值为 $A_1, A_2, \cdots, A_k$ 分别的真值表接受 $I$ 时输出的值的最大值。 - 如果 $A$ 是合式公式,则 $\lnot A$ 也是合式公式,设 $A$ 的真值表接受输入 $I$ 时输出 $x$,则 $\lnot A$ 的真值表接受 $I$ 时输出 $1 - x$。 定义一个合式公式的 **大小** 为其所包含的 $\land$ 和 $\lor$ 的数量。现给定一个道理,请找到一个合式公式,使得其真值表是该道理,在此前提下让公式的大小尽可能小。

输入输出格式

输入格式


**本题为提交答案题**,所有数据 `formula1.in` 至 `formula10.in` 已在附加文件中。 输入的第一行包含一个整数 $n$。 输入的第二行包含一个长度为 $2^n$ 的字符串 $a_{0 \sim 2^n - 1}$,描述给定的道理:如果对于任意 $0 \leq i < n$,输入的第 $i$ 个值是 $\left\lfloor\frac{x}{2^i}\right\rfloor \bmod 2$,则道理的输出为 $a_x$。 输入的第三行包含 $10$ 个评分参数,具体用处见「说明/提示」。

输出格式


针对给定的 $10$ 个输入文件,你需要分别提交你的输出文件 `formula1.out` 至 `formula10.out`。 每个输出文件包含一行,表示你给出的合式公式。其中括号用 `()` 表示,命题变项 $P_i$ 用数字 $i$ 表示(由于 $n \leq 10$,这一定是单个字符),$\land$ 用 `&` 表示,$\lor$ 用 `|` 表示,$\lnot$ 用 `!` 表示。**请不要擅自省略括号。**

输入输出样例

输入样例 #1

2
1101
1 1 1 1 1 1 1 1 1 1

输出样例 #1

(!1|0)

说明

对于所有数据,$1 \leq n \leq 10$。 对于每组数据,我们采用如下方式评分: - 如果你的输出长度大于 $10^5$,得 $0$ 分。 - 如果你的输出不是合式公式,得 $0$ 分。 - 如果你的合式公式的真值表与输入给定的道理不同,得 $0$ 分。 - 如果上述条件都不满足,设 $s_{1 \sim 10}$ 为评分参数,$S$ 为你的公式的大小,则得分为 $\sum_{i = 1}^{10}[S \leq s_i]$。 每组数据满分 $10$ 分,共 $10$ 组数据,总分 $100$ 分(乘以得分系数前)。**保证存在满分解**。 --- 我们提供了工具来测试你的输出。 下载附加文件 `checker.cpp` 并编译得到可执行文件 `checker.exe`(Windows)或 `checker`(Linux),其用法如下: - 在终端中输入 `checker.exe X`(Windows)或 `./checker X`(Linux),或直接运行后输入 `X` 并换行,可以对第 $X$ 组数据 `formulaX.in/out` 进行测试。 - 在终端中输入 `checker.exe A B`(Windows)或 `./checker A B`(Linux),或直接运行后输入 `A B` 并换行,可以对输入文件名为 $A$、输出文件名为 $B$ 的数据进行测试。 - 如果输入不合法或输出有错误,会有相应提示。 - 如果没有错误,则会给出你的合式公式的大小。 - 输入文件可以与输入格式的描述完全相符,也可以略去评分参数一行。若 checker 检测到存在评分参数一行,还会给出你的得分。 Source:NFLSPC #6 C by chenxia25