問題一覧 > 通常問題

No.359 門松行列

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 29
作問者 : koyumeishikoyumeishi / テスター : uwiuwi
0 ProblemId : 940 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-05-24 14:30:35

問題文

門松列 とは $3$ 個の要素からなる数列 $A_1, A_2, A_3$ で以下の 2 つの条件を満たすものです。

  • $A_1, A_2, A_3$ は全て異なる
  • $3$ つの要素の中で $A_2$ が最も大きい、または、$A_2$ が最も小さい

3次正方門松行列 とは、3次正方行列 $ A = \left( \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\\ a_{21} & a_{22} & a_{23} \\\ a_{31} & a_{32} & a_{33} \end{array} \right)$ で以下の条件を全て満たすものです。

  • 行列の全ての行について、数列 $a_{r1}, a_{r2}, a_{r3}$ ($r=1,2,3$) が門松列である
  • 行列の全ての列について、数列 $a_{1c}, a_{2c}, a_{3c}$ ($c=1,2,3$) が門松列である
  • 行列の反対角成分について、数列 $a_{13}, a_{22}, a_{31}$ が門松列である
  • 行列の対角成分について、数列 $a_{11}, a_{22}, a_{33}$ が門松列である
つまり、タテ、ヨコ、ナナメ に行列の成分を見たとき、全て門松列になっていることが条件です。

太郎君は $9$本の竹を $3 \times 3$ の枠に、長さが門松行列になるように配置しようとしています。
$7$本はすでに枠に配置しましたが、 あと$2$本竹が足りなかったので、竹林から長さ $L$ の竹を$1$本切り出してきました。
この切り出した竹を $2$つに分割 して枠に配置し、門松行列を完成させるとき、 何通りの門松行列が考えられるか太郎君に教えてあげてください。
ただし端数が出ると縁起が悪いので、分割後の竹の長さは正整数でなければなりません。 また、竹の切り方は「そぎ」ではなく「寸胴」(参考) なので、片方が$x$になるように分割したとき、もう一方は$L-x$になります。

入力

入力は全て整数で与えられます。
$T$

1行目にはテストケースの数$T (1 \leq T \leq 100)$が与えられます。

$L$
$a_{11}$ $a_{12}$ $a_{13}$
$a_{21}$ $a_{22}$ $a_{23}$
$a_{31}$ $a_{32}$ $a_{33}$

各テストケースの1行目には切り出された竹の長さ$L (1 \leq L \leq 10^9)$。 続く3行には枠に設置された竹の長さ$a_{ij} (0 \leq a_{ij} \leq 10^9)$が与えられます。
$a_{ij} = 0$ のとき、そこには未だ竹が配置されていません。
竹が未配置の場所は必ず $2$ 箇所だけ存在します。

出力

各テストケース毎、何通りの門松行列が考えられるか1行ずつ出力してください。

サンプル

サンプル1
入力
1
10
7 8 5
1 9 0
3 0 2
出力
1

$a_{23} = 6, a_{32} = 4$ の 1通り です。

サンプル2
入力
1
10
1 3 0
5 0 7
4 8 6
出力
0

どう頑張っても門松行列にはできないみたいです。

サンプル3
入力
4
3
4 0 8
6 9 2
5 0 7
10
0 1 1
0 1 1
1 1 1
6
1 5 4
0 10 1
3 1 0
38
20 16 17
0 12 14
19 14 0
出力
2
0
1
6

1つ目のケースは$a_{12} = 1, a_{32} = 2$のパターンと$a_{12} = 2, a_{32} = 1$のパターンの2通りです。
あけましておめでとうございます。

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