算法竞赛中时常会因为出题人的一些意义不明的问题(比如魔怔,比如缺乏同情心)而导致问题非常的extreme,包括但不限于以下情况:
-
在花费了好几张草稿纸后得到一个众所周知的结论,根据输入输出一个 的表达式。
-
题面长达四页,需要选手在冗长的阅读后模拟一个复杂系统的运行,比如桌游。
-
一个可以被证明不可解的问题,因为出题人的疏忽而放到了比赛中。
这道题也非常的extreme,因为这是一道关于极值(extremum)的问题。
为了简化问题,我们把所有讨论的点限定在 中的所有整点上。
定义一个局部极小值为满足如下所有条件的一个整点 :
同理可以定义局部极大值,只需要将上述定义中的小于号全部换成大于号。
定义平原为一个点,满足以下四个条件中至少一个:
值得注意的是,我们限定了点的范围在 上,所以任何这个范围以外的点被视为未定义,因此无法比较大小。也因此,边界上的点永远不可能成为局部极大值或局部极小值,但是它可能成为平原,因为平原只需要满足四个条件中的一个就行了。
接下来我们会告诉你下面的三个命题为真或否:
- 你的函数有至少两个局部极大值
- 你的函数有至少两个局部极小值
- 你的函数有若干平原。
然后,你需要构造一个有理二元函数,使它满足我们给出的条件。
特别的,你需要满足以下限制:
- 你需要以逆波兰表达式,即后缀表达式形式输出你的函数,关于逆波兰表达式,在下发的文件中会给出详细定义;
- 你的表达式中只能出现以下组成部分: 到 的闭区间内的整数。其中 表示乘法运算, 表示乘方运算,需要注意,我们不允许使用除号;
- 你应当用空格隔开你表达式中的不同部分,以免混淆负号和减号,同时,你的表达式应该由不超过 个组成部分构成。
当出现以下情况时,你的输出会被直接认定为错误:
- 读取到一个运算符,但左边已经没有足够的运算参数了;
- 乘方运算对某个数进行了负数次方;
- 某一步计算的结果溢出了32位有符号整数的表示范围;
- 在所有操作执行完之后,你剩余超过一个运算参数;
- 任何时候读取到一个不在上述参数列表中的参数;
- 其他任何不符合要求的输出。