luogu#P9927. [NFLSPC #6] 真理祭坛
[NFLSPC #6] 真理祭坛
题目背景
天色已晚,围观的人群散得差不多了。人们可能都没有注意到,还有一个瘦小的身影在向真理祭坛跑去。
「你是哪个领域的科学家?怎么就你一个人?」排险者歪了歪头,看着眼前的小 Y 问道。
「我不是科学家。我只是一个高中生。」
「学生?」排险者很困惑,「那你想问什么?」
「我想知道宇宙的终极规律。」
「既然你只是个学生,你认为我该如何让你理解宇宙的规律呢?」
「啊?」小 Y 似乎感到很惊讶,片刻之后,他的脸上出现了些许失望的神情。「宇宙的真理不应该简洁到每个人都能理解吗……难道不是吗?」
「真理可没这么简单。且不说宇宙,我在此随意给你一些『道理』,你能用简洁的语言描述它吗?」
小 Y 抬起头来,看着排险者用全息投影显示在天空中的几串密密麻麻的零和一,陷入了沉思。
题目描述
有 个 命题变项,记作 ,其 真值 是一个布尔值,要么为 要么为 。
我们称一个 道理 是一个输入 个布尔值、输出一个布尔值的函数,即一个 的映射。
满足特定条件的字符串称为 合式公式(Well-Formed Formula,WFF),每个合式公式都对应着唯一一个道理,称为该公式的 真值表。具体地:
- 一个命题变项 是合式公式,它的真值表总是输出其所接受的第 个输入值( 个输入值的编号依次为 )。
- 如果 个字符串 ()都是合式公式,则 也是合式公式,它的真值表在接受输入 时输出的值为 分别的真值表接受 时输出的值的最小值。
- 如果 个字符串 ()都是合式公式,则 也是合式公式,它的真值表在接受输入 时输出的值为 分别的真值表接受 时输出的值的最大值。
- 如果 是合式公式,则 也是合式公式,设 的真值表接受输入 时输出 ,则 的真值表接受 时输出 。
定义一个合式公式的 大小 为其所包含的 和 的数量。现给定一个道理,请找到一个合式公式,使得其真值表是该道理,在此前提下让公式的大小尽可能小。
输入格式
本题为提交答案题,所有数据 formula1.in
至 formula10.in
已在附加文件中。
输入的第一行包含一个整数 。
输入的第二行包含一个长度为 的字符串 ,描述给定的道理:如果对于任意 ,输入的第 个值是 ,则道理的输出为 。
输入的第三行包含 个评分参数,具体用处见「说明/提示」。
输出格式
针对给定的 个输入文件,你需要分别提交你的输出文件 formula1.out
至 formula10.out
。
每个输出文件包含一行,表示你给出的合式公式。其中括号用 ()
表示,命题变项 用数字 表示(由于 ,这一定是单个字符), 用 &
表示, 用 |
表示, 用 !
表示。请不要擅自省略括号。
2
1101
1 1 1 1 1 1 1 1 1 1
(!1|0)
提示
对于所有数据,。
对于每组数据,我们采用如下方式评分:
- 如果你的输出长度大于 ,得 分。
- 如果你的输出不是合式公式,得 分。
- 如果你的合式公式的真值表与输入给定的道理不同,得 分。
- 如果上述条件都不满足,设 为评分参数, 为你的公式的大小,则得分为 。
每组数据满分 分,共 组数据,总分 分(乘以得分系数前)。保证存在满分解。
我们提供了工具来测试你的输出。
下载附加文件 checker.cpp
并编译得到可执行文件 checker.exe
(Windows)或 checker
(Linux),其用法如下:
- 在终端中输入
checker.exe X
(Windows)或./checker X
(Linux),或直接运行后输入X
并换行,可以对第 组数据formulaX.in/out
进行测试。 - 在终端中输入
checker.exe A B
(Windows)或./checker A B
(Linux),或直接运行后输入A B
并换行,可以对输入文件名为 、输出文件名为 的数据进行测试。 - 如果输入不合法或输出有错误,会有相应提示。
- 如果没有错误,则会给出你的合式公式的大小。
- 输入文件可以与输入格式的描述完全相符,也可以略去评分参数一行。若 checker 检测到存在评分参数一行,还会给出你的得分。
Source:NFLSPC #6 C by chenxia25