#P4846. [neerc2016]Hard Refactoring

    ID: 3965 传统题 1000ms 128MiB 尝试: 42 已通过: 18 难度: 4 上传者: 标签>难度分类普及排序与序列处理差分标记区间修改贪心区间合并CF1400

[neerc2016]Hard Refactoring

题目描述

海伦发现一段代码,用包含许多数字常量的逻辑表达式判断整数 xx 是否落在若干区间里。样例 1 给出其中一个例子。

请重构给定的逻辑表达式。新表达式要在每个可能的 xx 上得到相同的布尔值,且表达式中出现的整数常量总数要尽可能少。所有整数(含 xx 及常量)的取值范围都是有符号 1616 位整数区间 [−215,215−1]=[−32768,32767][-2^{15},2^{15}-1]=[-32768,32767]。

输入格式

读至文件结束,至多 10001000 行。每行是一个比较式,或者是两个由逻辑与 && 连接的比较式。每个比较式由 x、>= 或 <=、一个整数常量组成。如果一行有两个比较式,第一个使用 >=,第二个使用 <=。

除最后一行外,每行末尾都有逻辑或运算符 ||。每行的相邻记号恰好用一个空格分隔,行首、行末没有空格。

输出格式

输出重构后的表达式。行的顺序任意,比较式、逻辑运算符及空格的格式与输入一致。输出的数不带前导零。对于范围内的每个整数 xx,重构表达式的布尔值必须与原式相同,并且出现的整数常量总数必须达到最小。

如果表达式对整个取值范围恒为真,输出一行 true。如果恒为假,输出一行 false。

样例 #1

输入 #1

x >= 5 && x <= 10 ||
x >= 7 && x <= 20 ||
x <= 2 ||
x >= 21 && x <= 25 ||
x >= 8 && x <= 10 ||
x >= 100

输出 #1

x <= 2 ||
x >= 5 && x <= 25 ||
x >= 100

样例 #2

输入 #2

x >= 10 && x <= 0

输出 #2

false

样例 #3

输入 #3

x <= 10 ||
x >= 0

输出 #3

true

样例 #4

输入 #4

x >= -32768

输出 #4

true