問題一覧 > 教育的問題

No.2976 Higher-Order Multipoint Evaluation

レベル : / AI推定難易度 : 1650 / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題　絶対誤差または相対誤差が $10^{-3}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : （AC するまで非表示） / 解いたユーザー数 5
作問者 : 👑 p-adic / テスター : ecottea
お気に入りにしたユーザー ProblemId : 10315 / 自分の提出
問題文最終更新日: 2024-12-02 20:11:13
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 454 (順位表) の他の問題:

Note

The time limit for this problem is 1000[ms].

Problem Statement

Define a function $f(x)$ of a real number $x$ by

$\displaystyle f(x) := \frac{1}{x^2 + 1} $

and consider the following problem:

You are given a non-negative integer $N$ and a real number $X$ as input.

$\displaystyle \frac{(X^2+1)^{\frac{N}{2} + 1}}{N!} \frac{d^N f}{d x^N}(X) $

Find the value above. Here, $\frac{d^N f}{d x^N}(X)$ denotes the $N$-th derivative of $f(x)$ at $X$.

　

A positive integer $T$ is given at the beginning of the input. Answer $T$ instances of the problem.

Constraints

For each positive integer $t$ not exceeding $T$, let $N_t, X_t$ denote the input values $N, X$ for the $t$-th problem, respectively.

Then, the input satisfies the following constraints:

  • $T$ is an integer satisfying $1 \leq T \leq 10^5$.
  • For any positive integer $t$ not exceeding $T$,
    • $N_t$ is an integer satisfying $0 \leq N_t \leq 200$.
    • $X_t$ is a real number such that $|X_t| < 1$ and $10^5 X_t$ is an integer.

Input

The input is given from standard input in $1 + T$ lines in the following format:

  • Line $1$ contains $T$.
  • For each positive integer $t$ not exceeding $T$, line $1 + t$ contains $N_t, X_t$ separated by a single space. Here, $X_t$ is given in the $5$-digit decimal representation explained below.
$T$
$N_1$ $X_1$
$\vdots$
$N_T$ $X_T$

The $5$-digit decimal representation of a real number $x$ is a decimal representation of $x$ whose fractional part has $5$ digits.

Click here for an explanation for those unfamiliar with decimal representations. (Click to expand)

　

The $5$-digit decimal representation of $x$ is a string $s$ satisfying the following:

  • There exists a sequence $(a_1,a_2,a_3,a_4,a_5)$ of length $5$ consisting only of non-negative integers not exceeding $9$ that satisfies all of the following:
    • If $x \geq 0$, then $x = \sum_{i=1}^{5} 10^{-i} a_i$.
    • If $x < 0$, then $x = - \sum_{i=1}^{5} 10^{-i} a_i$.
    • If $x > 0$, then $s = 0.a_1 a_2 a_3 a_4 a_5$.
    • If $x = 0$, then $s = 0.a_1 a_2 a_3 a_4 a_5$ or $s = -0.a_1 a_2 a_3 a_4 a_5$.
    • If $x < 0$, then $s = - 0.a_1 a_2 a_3 a_4 a_5$.

Note that the $5$-digit decimal representation of $x$ is neither guaranteed to be unique nor guaranteed to exist.

Output

For each positive integer $t$ not exceeding $T$, print the answer to the $t$-th problem on line $t$.

Print a newline at the end.

　

Note that this problem accepts answers with decimal error. Your answer is judged as correct if its absolute error or relative error from the approximation of the exact answer to $5$ decimal places is at most $10^{-3}$.

Here, the approximation of a real number $x$ to $5$ decimal places roughly means the decimal obtained by truncating the decimal representation of $x$ at the $5$-th decimal place.

Click here for a more precise explanation that does not use decimal representations. (Click to expand)

　

The approximation of $x$ to $5$ decimal places means:

  • if $x \geq 0$, the maximum real number $r$ such that $r \leq x$ and $10^5 r$ is an integer;
  • if $x < 0$, $-1$ times the approximation of $-x$ to $5$ decimal places.

　

Also, due to constraints on the judge side, your output must be fewer than $500$ digits.

Sample

Sample 1
Input
3
0 0.00000
1 -0.00000
2 0.10000
Output
1.00000
0.00000
-0.96039

The answer to the $1$st problem is

$\displaystyle \frac{(X_1^2+1)^{\frac{N_1}{2} + 1}}{N_1!} \frac{d^{N_1} f}{dx^{N_1}}(X_1) = \frac{(0.00000^2+1)^{\frac{0}{2} + 1}}{0!} \frac{d^0 f}{dx^0}(0.00000) = 1 \times \left. \frac{1}{x^2+1} \right|_{x = 0.00000} = \frac{1}{0.00000^2+1} = 1 $

For example, $1.001$ and $0.999$ are also accepted.

　

The answer to the $2$nd problem is

$\displaystyle \frac{(X_2^2+1)^{\frac{N_2}{2} + 1}}{N_2!} \frac{d^{N_2} f}{dx^{N_2}}(X_2) = \frac{((-0.00000)^2+1)^{\frac{1}{2} + 1}}{1!} \frac{d^1 f}{dx^1}(-0.00000) = 1^{\frac{3}{2}} \left. \frac{d}{dx} \frac{1}{x^2+1} \right|_{x = -0.00000} = 1 \times \left( \left. - \frac{2x}{(x^2+1)^2} \right|_{x = -0.00000} \right) = - \frac{2 \times (-0.00000)}{((-0.00000)^2+1)^2} = 0 $

For example, $0.001$ and $-0.001$ are also accepted.

　

The answer to the $3$rd problem is

$\displaystyle \begin{array}{rcl} \displaystyle \frac{(X_3^2+1)^{\frac{N_3}{2} + 1}}{N_3!} \frac{d^{N_3} f}{dx^{N_3}}(X_3) &\displaystyle = &\displaystyle \frac{(0.10000^2+1)^{\frac{2}{2} + 1}}{2!} \frac{d^2 f}{dx^2}(0.10000) = \frac{1.01^2}{2} \left. \frac{d^2}{dx^2} \frac{1}{x^2+1} \right|_{x = 0.10000} = 0.51005 \left. \frac{d}{dx} \left( - \frac{2x}{(x^2+1)^2} \right) \right|_{x = 0.10000} \\ & & \\ &\displaystyle = &\displaystyle 0.51005 \left. \frac{6x^2-2}{(x^2+1)^3} \right|_{x = 0.10000} = 0.51005 \times \frac{6 \times 0.10000^2 - 2}{((0.10000)^2+1)^3} = 0.51005 \times (-1.882944 \cdots) = -0.960396 \cdots \end{array} $

For example, $-0.960$ and $-0.961$ are also accepted.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。