No.2447 Matrix Power Root
Problem Statement
First, let us introduce some terminology. A $(1,5)$-digit decimal representation of a real number $x$ is a decimal representation of $x$ whose integer part and fractional part have $1$ digit and $5$ digits, respectively.
Here is an explanation for those unfamiliar with decimal representations. (Click to expand)
A $(1,5)$-digit decimal representation of $x$ is a string $s$ satisfying the following:
- There exists a sequence $(a_0,a_1,a_2,a_3,a_4,a_5)$ of length $6$ consisting only of non-negative integers at most $9$ that satisfies all of the following:
- If $x \geq 0$, then $x = \sum_{i=0}^{5} 10^{-i} a_i$.
- If $x < 0$, then $x = - \sum_{i=0}^{5} 10^{-i} a_i$.
- If $x > 0$, then $s = a_0.a_1 a_2 a_3 a_4 a_5$.
- If $x = 0$, then $s = a_0.a_1 a_2 a_3 a_4 a_5$ or $s = -a_0.a_1 a_2 a_3 a_4 a_5$.
- If $x < 0$, then $s = - a_0.a_1 a_2 a_3 a_4 a_5$.
Note that a $(1,5)$-digit decimal representation of $x$ is neither guaranteed to be unique nor guaranteed to exist.
An approximate $3$rd root of a real square matrix $M$ of order $2$ is a real square matrix $N$ of order $2$ satisfying both of the following $2$ conditions:
- The absolute value of each entry of $M - N^3$ is less than $10^{-3}$.
- Each entry of $N$ has a $(1,5)$-digit decimal representation.
Now, consider the following problem:
A real symmetric matrix $M$ of order $2$ is given as input.
Determine whether an approximate $3$rd root of $M$ exists, and if it exists, find $1$ of them.
A positive integer $T$ is given at the beginning of the input. Answer $T$ problems.
Input
Below, for each positive integer $t$ at most $T$, the input for the $t$-th problem is denoted by $M_t$. Also, for a real square matrix $M$ of order $2$ and positive integers $i,j$ at most $2$, $M_{i,j}$ denotes the $(i,j)$ entry of $M$.
The input is given from standard input in $1 + 2T$ lines in the following format:
- Line $1$ contains $T$.
- For each positive integer $t$ at most $T$, lines $2t$ through $2t+1$ contain the input for the $t$-th problem.
$T$ ($1$ 個目の問題に対する入力) $\vdots$ ($T$ 個目の問題に対する入力)
Here, for each positive integer $t$ at most $T$, the input for the $t$-th problem is given from standard input in $2$ lines (lines $2t$ through $2t + 1$ of the entire input) in the following format:
- Line $1$ contains $(1,5)$-digit decimal representations of $(M_t)_{1,1}, (M_t)_{1,2}$, separated by a single-byte space.
- Line $2$ contains $(1,5)$-digit decimal representations of $(M_t)_{2,1}, (M_t)_{2,2}$, separated by a single-byte space.
$(M_t)_{1,1}$ $(M_t)_{1,2}$
$(M_t)_{2,1}$ $(M_t)_{2,2}$
Constraints
The input satisfies the following constraints:
- $T$ is a positive integer satisfying $1 \leq T \leq 10^5$.
- For each positive integer $t$ at most $T$, the input $M_t$ for the $t$-th problem satisfies the following:
- $M_t$ is a real symmetric matrix of order $2$.
- Each entry of $M_t$ has a $(1,5)$-digit decimal representation.
Output
For each positive integer $t$ at most $T$, print the answer to the $t$-th problem on lines $2t-1$ and $2t$ in the following format:
- If no approximate $3$rd root of $M_t$ exists, print
Noon both line $2t-1$ and line $2t$.
No No
- On line $2t-1$, print $(1,5)$-digit decimal representations of $(N_t)_{1,1}, (N_t)_{1,2}$, separated by a single-byte space.
- On line $2t$, print $(1,5)$-digit decimal representations of $(N_t)_{2,1}, (N_t)_{2,2}$, separated by a single-byte space.
$(N_t)_{1,1}$ $(N_t)_{1,2}$
$(N_t)_{2,1}$ $(N_t)_{2,2}$
This problem uses a special judge. There may be more than $1$ correct answer, but print only $1$ of them.
Print a newline at the end.
Sample
Sample 1
Input
1 0.00000 0.00000 0.00000 0.00000
Output
0.00000 0.00000 0.00000 0.00000
$ \left( \begin{array}{cc} \displaystyle 0.00000 &\displaystyle 0.00000 \\ \displaystyle 0.00000 &\displaystyle 0.00000 \end{array} \right)^3 - \left( \begin{array}{cc} \displaystyle 0.00000 &\displaystyle 0.00000 \\ \displaystyle 0.00000 &\displaystyle 0.00000 \end{array} \right) = \left( \begin{array}{cc} \displaystyle 0.00000 &\displaystyle 0.00000 \\ \displaystyle 0.00000 &\displaystyle 0.00000 \end{array} \right) $
holds. Besides this output, outputs such as
0.00001 0.00001 0.00001 0.00001
and
0.00000 9.99999 -0.00000 0.00000
are also correct. Since $T = 1$ here, all the problems have now been answered.
Sample 2
Input
1 1.00000 0.00000 0.00000 1.00000
Output
1.00000 0.00000 0.00000 1.00000
$ \left( \begin{array}{cc} \displaystyle 1.00000 &\displaystyle 0.00000 \\ \displaystyle 0.00000 &\displaystyle 1.00000 \end{array} \right)^3 - \left( \begin{array}{cc} \displaystyle 1.00000 &\displaystyle 0.00000 \\ \displaystyle 0.00000 &\displaystyle 1.00000 \end{array} \right) = \left( \begin{array}{cc} \displaystyle 0.00000 &\displaystyle 0.00000 \\ \displaystyle 0.00000 &\displaystyle 0.00000 \end{array} \right) $
holds. Since $T = 1$ here, all the problems have now been answered.
Sample 3
Input
2 1.00000 0.00000 0.00000 -1.00000 1.00000 -0.00000 -0.00000 -1.00000
Output
1.00000 0.00000 0.00000 -1.00000 1.00000 -0.00000 -0.00000 -1.00000
$ \left( \begin{array}{cc} \displaystyle 1.00000 &\displaystyle 0.00000 \\ \displaystyle 0.00000 &\displaystyle -1.00000 \end{array} \right)^3 - \left( \begin{array}{cc} \displaystyle 1.00000 &\displaystyle 0.00000 \\ \displaystyle 0.00000 &\displaystyle -1.00000 \end{array} \right) = \left( \begin{array}{cc} \displaystyle 0.00000 &\displaystyle 0.00000 \\ \displaystyle 0.00000 &\displaystyle 0.00000 \end{array} \right) $
holds. Since $T = 2$ here, all the problems have now been answered.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
hotman78