← 返回题目列表

Codeforces · 39/G

G. 反函数

中文机器翻译题面 查看原题

Petya 用 C++ 编写了一个程序,计算了一个非常有趣的函数 f(n)。 Petya 以一定的 n 值运行程序,然后去厨房喝茶。历史上没有关于该计划运行了多久的记录。等Petya回来的时候,它已经完成了计算并得出了结果。然而,当 Petya 喝茶时,一种狡猾的病毒设法破坏了输入文件,使 Petya 无法弄清楚程序运行时的 n 值。帮助 Petya,执行反函数!

该程序主要由 C++ 函数组成,具有以下简化语法:

- 函数 ::= int f(int n) {operatorSequence}
- 运算符序列 ::= 运算符 | 运算符 运算符序列
- 运算符 ::= 返回 arithmExpr; | if (逻辑表达式) 返回 arithmExpr;
- 逻辑表达式 ::= arithmExpr > arithmExpr | arithmExpr < arithmExpr | arithmExpr == arithmExpr
- arithmExpr ::= 总和
- 总和 ::= 产品 |总和 + 乘积|和 - 积
- 产品 ::= 乘数 |乘积 * 乘数 |乘积 / 乘数
- 乘数 ::= n |数量 | f(算术表达式)
- 数字 ::= 0|1|2|... |32767

运算符序列中的空格是可选的。

因此,我们有一个函数,其中有两种运算符。有运算符“return arithmExpr;”返回表达式的值作为函数的值,并且有条件运算符“if (逻辑Expr) return arithmExpr;”当且仅当逻辑表达式为真时才返回算术表达式的值。确保函数中不使用 C++ 语言的其他结构——循环、赋值运算符、嵌套条件运算符等以及除 n 参数之外的其他变量。所有常量都是区间 [0..32767] 内的整数。

运算符按顺序执行。函数返回值后,不会执行序列中的其他运算符。执行算术表达式时考虑到操作的标准优先级。这意味着首先计算总和中的所有乘积。在乘积计算过程中,乘法和除法运算是从左到右执行的。然后将被加数相加,加减法也是从左到右进行。操作“">”(更多)、“<”(更少)和“==”(等于)也具有标准含义。

现在你必须密切注意!该程序是在 Berland 公司 BerSoft 发明的 15 位 Berland C++ 编译器的帮助下编译的,这就是算术运算以非标准方式执行的原因。加法、减法和乘法以 32768 为模(如果减法结果为负,则加上 32768,直到该数字属于区间 [0..32767])。除法“/”是通常的整数除法,其中余数被省略。

算术运算示例:

$$12345+23456=3033,\四元0-1=32767,\四元1024*1024=0,\四元1000/3=333。$$

保证对于 0 到 32767 之间的所有 n 值,给定的函数都能正确执行。这意味着:

1. 永远不会发生除以 0 的情况。

2. 当对值 n = N 执行函数时,函数 f 的递归调用可能仅针对参数值 0, 1, ..., N - 1 发生。因此,程序永远不会出现无限递归。

3. 作为运算符序列的结果,该函数始终返回一个值。

我们必须提到,由于所有的限制,函数 f 返回的值独立于全局变量或作为逻辑表达式的一部分执行算术表达式计算的顺序,或者独立于除 n 参数值之外的任何其他值。这就是为什么 f 函数可以被视为数学意义上的函数,即区间 [0..32767] 中的任何 n 值与同一区间中的 f(n) 值之间的唯一对应关系。

给定 f(n) 的值,您应该找到 n。如果合适的 n 值不唯一,您应该找到最大的值(从区间 [0..32767] 中)。

输入

第一行有一个来自区间 [0..32767] 的整数 f(n)。接下来的几行是函数 f 的描述。在描述中可以找到额外的空格和换行符(参见示例),当然,它们不能破坏关键字 int、if、return 和数字。输入数据的大小不能超过100字节。

输出

输出一个数字——问题的答案。如果没有答案,则输出“-1”(不带引号)。

示例

输入 #1

17
int f(int n)
{
if (n < 100) return 17;
if (n > 99) return 27;
}

输出 #1

99

输入 #2

13
int f(int n)
{
if (n == 0) return 0;
return f(n - 1) + 1;
}

输出 #2

13

输入 #3

144
int f(int n)
{
if (n == 0) return 0;
if (n == 1) return n;
return f(n - 1) + f(n - 2);
}

输出 #3

24588