#1340. Extreme Problem

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Rhodoks

题目描述

算法竞赛中时常会因为出题人的一些意义不明的问题(比如魔怔,比如缺乏同情心)而导致问题非常的extreme,包括但不限于以下情况:

  • 在花费了好几张草稿纸后得到一个众所周知的结论,根据输入输出一个 的表达式。

  • 题面长达四页,需要选手在冗长的阅读后模拟一个复杂系统的运行,比如桌游。

  • 一个可以被证明不可解的问题,因为出题人的疏忽而放到了比赛中。

这道题也非常的extreme,因为这是一道关于极值(extremum)的问题。

为了简化问题,我们把所有讨论的点限定在 中的所有整点上。

定义一个局部极小值为满足如下所有条件的一个整点

同理可以定义局部极大值,只需要将上述定义中的小于号全部换成大于号。

定义平原为一个点,满足以下四个条件中至少一个:

值得注意的是,我们限定了点的范围在 上,所以任何这个范围以外的点被视为未定义,因此无法比较大小。也因此,边界上的点永远不可能成为局部极大值或局部极小值,但是它可能成为平原,因为平原只需要满足四个条件中的一个就行了。

接下来我们会告诉你下面的三个命题为真或否:

  1. 你的函数有至少两个局部极大值
  2. 你的函数有至少两个局部极小值
  3. 你的函数有若干平原。

然后,你需要构造一个有理二元函数,使它满足我们给出的条件。

特别的,你需要满足以下限制:

  • 你需要以逆波兰表达式,即后缀表达式形式输出你的函数,关于逆波兰表达式,在下发的文件中会给出详细定义;
  • 你的表达式中只能出现以下组成部分: 的闭区间内的整数。其中 表示乘法运算, 表示乘方运算,需要注意,我们不允许使用除号;
  • 你应当用空格隔开你表达式中的不同部分,以免混淆负号和减号,同时,你的表达式应该由不超过 个组成部分构成。

当出现以下情况时,你的输出会被直接认定为错误:

  • 读取到一个运算符,但左边已经没有足够的运算参数了;
  • 乘方运算对某个数进行了负数次方;
  • 某一步计算的结果溢出了32位有符号整数的表示范围;
  • 在所有操作执行完之后,你剩余超过一个运算参数;
  • 任何时候读取到一个不在上述参数列表中的参数;
  • 其他任何不符合要求的输出。

输入格式

输入包含三行:

第一行以 Multiple local maxima: 开头,随后是一个字符串,只可能是 YesNo 中的一种,表示回答的函数是否有多个局部极大值。

第二行以 Multiple local minima: 开头,随后是一个字符串,只可能是 YesNo 中的一种,表示回答的函数是否有多个局部极小值。

第三行以 Plateaus: 开头,随后是一个字符串,只可能是 YesNo 中的一种,表示回答的函数是否有若干平原。

输出格式

可以证明输入的任何情况有解。

输出一行一个逆波兰表达式,表示你构造的二元有理函数。

你需要满足题面中的所有条件。

样例

样例输入1

Multiple local maxima: No
Multiple local minima: No
Plateaus: No

样例输出1

x 3 - 4 ^ y -5 + 2 ^ +

样例输入2

Multiple local maxima: No
Multiple local minima: No
Plateaus: Yes

样例输出2

1