QOJ.ac

QOJ

时间限制: 1.0 s 内存限制: 1024 MB 总分: 100 可 Hack ✓

#10118. 表达式

统计

矮人的传奇机械制造技术使他们能够制造出早于巴贝奇分析机的机械计算设备。然而最近,极简主义趋势盛行,一些人建议用指令集更精简的简单机器来替代这些复杂的机器,因为它们应该更小、更便宜,并且在运行速度上可能也显著更快。到目前为止,矮人们还无法确定足以执行他们认为重要的所有计算的最小操作集。为了解决这个问题,他们决定进行大量的测试。你需要解决其中的一些测试,你的目标是尽可能将给定的表达式重写为仅使用指定操作符子集的等价表达式。

你将获得一个由二元操作符 minmax<=< 和变量(英文字母表的前 10 个字母)组成的表达式。变量集合 $S$ 的赋值定义为给 $S$ 中的每个元素分配一个 0 或 1 的值。如果满足以下两个条件,我们称两个表达式是等价的:

  • 表达式中出现的变量集合相同——记该集合为 $S$,
  • 对于 $S$ 的每一种赋值,代入值后的两个表达式计算结果相同。

你的任务是创建一个仅由操作符 min<= 组成的表达式,使其与输入表达式等价,或者指出这样的表达式不存在。

输入格式

标准输入的第一行也是唯一一行包含一个表达式。它是一个符合以下文法的 expr

  • var := a | b | ... | j
  • op := expr <= expr | expr < expr | min expr expr | max expr expr
  • expr := var | (op)

数据范围

给定表达式包含最多 200 个二元操作。

输出格式

如果存在解,在第一行输出 YES,并在第二行输出任意一个由最多 40 000 个二元操作组成的等价表达式。否则,输出一行 NO

说明:可以证明,如果存在任意大小的解,则一定存在一个由最多 40 000 个操作组成的解。

样例

样例输入 1

h

样例输出 1

YES
h

样例输入 2

((max a a) <= b)

样例输出 2

YES
(a <= b)

样例输入 3

((max a b) < (min a b))

样例输出 3

NO

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.