Mika 教授是一位计算机科学研究员,他提出了以下问题:给定 $n$ 个 $(x, y)$ 数对(其中 $1 \le n \le 20$),如何找到一个能够拟合所有这些数对的控制方程 $y = f(x)$?换句话说,他试图确定一个包含二元运算符($+$, $-$, $\times$, $\div$)、一元运算符($\sin$, $\cos$)、符号 $x$ 以及括号的方程,使其能够拟合所有给定的数对。例如,$y = x \times x \div \sin(x)$ 或 $y = x \times (x + x \div x)$。
为了生成所有合法的方程,我们定义如下上下文无关文法:
- 起始符号为 $S$。
- $S \to S + S \mid S - S$
- $S \to S \times S \mid S \div S$
- $S \to \sin(S) \mid \cos(S)$
- $S \to (S) \mid x$
然而,为了防止过拟合,我们将方程的复杂度限制在 9 以内。复杂度定义为:二元运算符($+$, $-$, $\times$, $\div$)的数量乘以 2,加上一元运算符($\sin$, $\cos$)的数量乘以 1。例如,方程 $x + (x + x \times x)$ 的复杂度为 6,而 $x \times \sin(x)$ 的复杂度为 3。只有复杂度小于或等于 9 的方程才会被视为正确。
输入格式
第一行包含一个整数 $n$ ($1 \le n \le 20$),表示需要拟合的 $(x, y)$ 数对的数量。
接下来的 $n$ 行,每行包含两个实数 $x, y$ ($|x|, |y| < 10^3$),且小数点后恰好有六位数字,表示 $(x, y)$ 数对。
保证 $x$ 的值是精确的,且我们使用某个合法的方程生成 $y$ 的值,然后将其四舍五入到小数点后六位。
输出格式
输出仅包含一行表达式 $f$,由 ‘+’、‘-’、‘*’(代表 $\times$)、‘/’(代表 $\div$)、‘sin’、‘cos’、‘x’、‘(’ 和 ‘)’ 组成。
如果你的答案满足以下条件,将被视为正确:
- 表达式 $f$ 是根据上述上下文无关文法生成的,并且符合该文法。
- 表达式 $f$ 的复杂度不超过 9,且长度不超过 1000 个字符。
- 对于每个 $(x, y)$ 数对,$f(x)$ 与 $y$ 之间的绝对误差或相对误差不大于 $10^{-3}$,即 $\frac{|f(x)-y|}{\max(1,|y|)} \le 10^{-3}$。
- 在计算除法运算时,被除数的绝对值必须不小于 0.01。
$f(x)$ 的求值遵循标准数学惯例:括号内的表达式优先计算,其次是乘法和除法(优先级高于加法和减法),且所有二元运算符均为左结合。
我们用于生成数据的方程保证在测试中满足上述所有四个要求。此外,为了避免可能的浮点数问题,对于第四个要求,我们承诺解满足更严格的 0.02 边界。
注意,本题可能存在多个合法的解,任何一个合法的解都会被接受。
样例
样例输入 1
3 1.000000 1.000000 2.000000 4.000000 3.000000 9.000000
样例输出 1
x*x
样例输入 2
3 0.618000 1.517072 0.314000 3.132637 1.414000 0.494016
样例输出 2
sin(x)/(x*x)