QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100

#6395. 方程发现

Statistics

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)$。

为了生成所有合法的方程,我们定义如下上下文无关文法:

  1. 起始符号为 $S$。
  2. $S \to S + S \mid S - S$
  3. $S \to S \times S \mid S \div S$
  4. $S \to \sin(S) \mid \cos(S)$
  5. $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’、‘(’ 和 ‘)’ 组成。

如果你的答案满足以下条件,将被视为正确:

  1. 表达式 $f$ 是根据上述上下文无关文法生成的,并且符合该文法。
  2. 表达式 $f$ 的复杂度不超过 9,且长度不超过 1000 个字符。
  3. 对于每个 $(x, y)$ 数对,$f(x)$ 与 $y$ 之间的绝对误差或相对误差不大于 $10^{-3}$,即 $\frac{|f(x)-y|}{\max(1,|y|)} \le 10^{-3}$。
  4. 在计算除法运算时,被除数的绝对值必须不小于 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)

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.