問題一覧 > 教育的問題

No.2447 Matrix Power Root

レベル : / AI推定難易度 : 1550 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 6
作問者 : 👑 p-adic / テスター : hotman78
お気に入りにしたユーザー ProblemId : 9464 / 自分の提出
問題文最終更新日: 2023-08-30 09:55:32
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 402 (順位表) の他の問題:

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:

  1. The absolute value of each entry of $M - N^3$ is less than $10^{-3}$.
  2. 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 No on both line $2t-1$ and line $2t$.
  • No
    No
    
  • If an approximate $3$rd root of $M_t$ exists, let $N_t$ be $1$ of them, and:
    • 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もしくは右上の雲マークをクリックしてアカウントを作成してください。