{"problem":{"name":"[NFLSPC #6] 真理祭坛","description":{"content":"有 $n$ 个 **命题变项**，记作 $P_0, P_1, \\cdots, P_{n - 1}$，其 **真值** 是一个布尔值，要么为 $0$ 要么为 $1$。 我们称一个 **道理** 是一个输入 $n$ 个布尔值、输出一个布尔值的函数，即一个 $\\{0, 1\\}^n \\to \\{0, 1\\}$ 的映射。 满足特定条件的字符串称为 **合式公式**（Well-Formed Formula","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9927"},"statements":[{"statement_type":"Markdown","content":"有 $n$ 个 **命题变项**，记作 $P_0, P_1, \\cdots, P_{n - 1}$，其 **真值** 是一个布尔值，要么为 $0$ 要么为 $1$。\n\n我们称一个 **道理** 是一个输入 $n$ 个布尔值、输出一个布尔值的函数，即一个 $\\{0, 1\\}^n \\to \\{0, 1\\}$ 的映射。\n\n满足特定条件的字符串称为 **合式公式**（Well-Formed Formula，WFF），每个合式公式都对应着唯一一个道理，称为该公式的 **真值表**。具体地：\n\n- 一个命题变项 $P_i$ 是合式公式，它的真值表总是输出其所接受的第 $i$ 个输入值（$n$ 个输入值的编号依次为 $0, 1, \\cdots, n - 1$）。\n- 如果 $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$ 时输出的值的最小值。\n- 如果 $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$ 时输出的值的最大值。\n- 如果 $A$ 是合式公式，则 $\\lnot A$ 也是合式公式，设 $A$ 的真值表接受输入 $I$ 时输出 $x$，则 $\\lnot A$ 的真值表接受 $I$ 时输出 $1 - x$。\n\n定义一个合式公式的 **大小** 为其所包含的 $\\land$ 和 $\\lor$ 的数量。现给定一个道理，请找到一个合式公式，使得其真值表是该道理，在此前提下让公式的大小尽可能小。\n\n## Input\n\n**本题为提交答案题**，所有数据 `formula1.in` 至 `formula10.in` 已在附加文件中。\n\n输入的第一行包含一个整数 $n$。\n\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$。\n\n输入的第三行包含 $10$ 个评分参数，具体用处见「说明/提示」。\n\n## Output\n\n针对给定的 $10$ 个输入文件，你需要分别提交你的输出文件 `formula1.out` 至 `formula10.out`。\n\n每个输出文件包含一行，表示你给出的合式公式。其中括号用 `()` 表示，命题变项 $P_i$ 用数字 $i$ 表示（由于 $n \\leq 10$，这一定是单个字符），$\\land$ 用 `&` 表示，$\\lor$ 用 `|` 表示，$\\lnot$ 用 `!` 表示。**请不要擅自省略括号。**\n\n[samples]\n\n## Background\n\n天色已晚，围观的人群散得差不多了。人们可能都没有注意到，还有一个瘦小的身影在向真理祭坛跑去。\n\n「你是哪个领域的科学家？怎么就你一个人？」排险者歪了歪头，看着眼前的小 Y 问道。\n\n「我不是科学家。我只是一个高中生。」\n\n「学生？」排险者很困惑，「那你想问什么？」\n\n「我想知道宇宙的终极规律。」\n\n「既然你只是个学生，你认为我该如何让你理解宇宙的规律呢？」\n\n「啊？」小 Y 似乎感到很惊讶，片刻之后，他的脸上出现了些许失望的神情。「宇宙的真理不应该简洁到每个人都能理解吗……难道不是吗？」\n\n「真理可没这么简单。且不说宇宙，我在此随意给你一些『道理』，你能用简洁的语言描述它吗？」\n\n小 Y 抬起头来，看着排险者用全息投影显示在天空中的几串密密麻麻的零和一，陷入了沉思。\n\n## Note\n\n对于所有数据，$1 \\leq n \\leq 10$。\n\n对于每组数据，我们采用如下方式评分：\n\n- 如果你的输出长度大于 $10^5$，得 $0$ 分。\n- 如果你的输出不是合式公式，得 $0$ 分。\n- 如果你的合式公式的真值表与输入给定的道理不同，得 $0$ 分。\n- 如果上述条件都不满足，设 $s_{1 \\sim 10}$ 为评分参数，$S$ 为你的公式的大小，则得分为 $\\sum_{i = 1}^{10}[S \\leq s_i]$。\n\n每组数据满分 $10$ 分，共 $10$ 组数据，总分 $100$ 分（乘以得分系数前）。**保证存在满分解**。\n\n---\n\n我们提供了工具来测试你的输出。\n\n下载附加文件 `checker.cpp` 并编译得到可执行文件 `checker.exe`（Windows）或 `checker`（Linux），其用法如下：\n\n- 在终端中输入 `checker.exe X`（Windows）或 `./checker X`（Linux），或直接运行后输入 `X` 并换行，可以对第 $X$ 组数据 `formulaX.in/out` 进行测试。\n- 在终端中输入 `checker.exe A B`（Windows）或 `./checker A B`（Linux），或直接运行后输入 `A B` 并换行，可以对输入文件名为 $A$、输出文件名为 $B$ 的数据进行测试。\n- 如果输入不合法或输出有错误，会有相应提示。\n- 如果没有错误，则会给出你的合式公式的大小。\n- 输入文件可以与输入格式的描述完全相符，也可以略去评分参数一行。若 checker 检测到存在评分参数一行，还会给出你的得分。\n\nSource：NFLSPC #6 C by chenxia25","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9927","tags":["提交答案","Special Judge"],"sample_group":[["2\n1101\n1 1 1 1 1 1 1 1 1 1\n","(!1|0)\n"]],"created_at":"2026-03-03 11:09:25"}}