No.2447 行列累乗根
タグ : / 解いたユーザー数 6
作問者 : 👑
p-adic
/ テスター :
hotman78
問題文
まずは用語の導入です。実数 $x$ の $(1,5)$ 桁小数表示とは、$x$ の小数表示であって整数部分と小数部分がそれぞれ $1$ 桁と $5$ 桁であるもののことです。
小数表示について知らない人向けの説明はこちらです。（クリックで開く）
$x$ の $(1,5)$ 桁小数表示とは、以下を満たす文字列 $s$ のことです：
- $9$ 以下の非負整数のみからなる長さ $6$ の数列 $(a_0,a_1,a_2,a_3,a_4,a_5)$ であって以下の全てを満たすものが存在する：
- $x \geq 0$ ならば、$x = \sum_{i=0}^{5} 10^{-i} a_i$ である。
- $x < 0$ ならば、$x = - \sum_{i=0}^{5} 10^{-i} a_i$ である。
- $x > 0$ ならば、$s = a_0.a_1 a_2 a_3 a_4 a_5$ である。
- $x = 0$ ならば、$s = a_0.a_1 a_2 a_3 a_4 a_5$ または $s = -a_0.a_1 a_2 a_3 a_4 a_5$ である。
- $x < 0$ ならば、$s = - a_0.a_1 a_2 a_3 a_4 a_5$ である。
ただし $x$ の $(1,5)$ 桁小数表示は一意であるとも存在するとも限らないことに注意してください。
実数係数 $2$ 次正方行列 $M$ の近似的 $3$ 乗根とは、以下の $2$ 条件を全て満たす実数係数 $2$ 次正方行列 $N$ のことです：
- $M - N^3$ の各成分の絶対値が $10^{-3}$ 未満である。
- $N$ の各成分は $(1,5)$ 桁小数表示を持つ。
ここで、次の問題を考えます：
入力に実数係数 $2$ 次対称行列 $M$ が与えられます。
$M$ の近似的 $3$ 乗根が存在するか否かを判定し、存在する場合は $1$ つ求めてください。
入力の最初に正整数 $T$ が与えられます。$T$ 個の問題に答えてください。
入力
以下、$T$ 以下の各正整数 $t$ に対し、$t$ 個目の問題に対する入力を $M_t$ と表します。また実数係数 $2$ 次正方行列 $M$ と $2$ 以下の正整数 $i,j$ に対し、$M_{i,j}$ で $M$ の $(i,j)$ 成分を表します。
入力は以下の形式で標準入力から $1 + 2T$ 行で与えられます：
- $1$ 行目に $T$ が与えられます。
- $T$ 以下の各正整数 $t$ に対し、$2t$ 行目から $2t+1$ 行目までに $t$ 個目の問題に対する入力が与えられます。
$T$ ($1$ 個目の問題に対する入力) $\vdots$ ($T$ 個目の問題に対する入力)
ここで $T$ 以下の各正整数 $t$ に対し、$t$ 個目の問題に対する入力は以下の形式で標準入力から $2$ 行（入力全体の $2t$ 行目から $2t + 1$ 行目まで）で与えられます：
- $1$ 行目に $(M_t)_{1,1}, (M_t)_{1,2}$ の $(1,5)$ 桁小数表示が半角空白区切りで与えられます。
- $2$ 行目に $(M_t)_{2,1}, (M_t)_{2,2}$ の $(1,5)$ 桁小数表示が半角空白区切りで与えられます。
$(M_t)_{1,1}$ $(M_t)_{1,2}$
$(M_t)_{2,1}$ $(M_t)_{2,2}$
制約
入力は以下の制約を満たします：
- $T$ は $1 \leq T \leq 10^5$ を満たす正整数である。
- $T$ 以下の各正整数 $t$ に対し、$t$ 個目の問題に対する入力 $M_t$ は以下を満たす：
- $M_t$ は実数係数 $2$ 次対称行列である。
- $M_t$ の各成分は $(1,5)$ 桁小数表示を持つ。
出力
$T$ 以下の各正整数 $t$ に対し、$t$ 個目の問題に対する回答を以下の形式で $2t-1$ 行目と $2t$ 行目に出力してください：
- $M_t$ の近似的 $3$ 乗根が存在しないならば、$2t-1$ 行目と $2t$ 行目の両方に
Noと出力してください。
No No
- $2t-1$ 行目に $(N_t)_{1,1}, (N_t)_{1,2}$ の $(1,5)$ 桁小数表示を半角空白区切りで出力してください。
- $2t$ 行目に $(N_t)_{2,1}, (N_t)_{2,2}$ の $(1,5)$ 桁小数表示を半角空白区切りで出力してください。
$(N_t)_{1,1}$ $(N_t)_{1,2}$
$(N_t)_{2,1}$ $(N_t)_{2,2}$
なおこの問題はスペシャルジャッジ問題です。正解は $1$ つではないかもしれませんが、$1$ つだけ出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 0.00000 0.00000 0.00000 0.00000
出力
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) $
です。この他にも
0.00001 0.00001 0.00001 0.00001
や
0.00000 9.99999 -0.00000 0.00000
などが正解です。今回は $T = 1$ なのでこれで全ての問題に答えられました。
サンプル2
入力
1 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) $
です。今回は $T = 1$ なのでこれで全ての問題に答えられました。
サンプル3
入力
2 1.00000 0.00000 0.00000 -1.00000 1.00000 -0.00000 -0.00000 -1.00000
出力
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) $
です。今回は $T = 2$ なのでこれで全ての問題に答えられました。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。