問題一覧 > 通常問題

No.359 門松行列

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

問題文

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

  • A1,A2,A3 は全て異なる
  • 3 つの要素の中で A2 が最も大きい、または、A2 が最も小さい

3次正方門松行列 とは、3次正方行列 A=(a11a12a13 a21a22a23 a31a32a33) で以下の条件を全て満たすものです。

  • 行列の全ての行について、数列 ar1,ar2,ar3 (r=1,2,3) が門松列である
  • 行列の全ての列について、数列 a1c,a2c,a3c (c=1,2,3) が門松列である
  • 行列の反対角成分について、数列 a13,a22,a31 が門松列である
  • 行列の対角成分について、数列 a11,a22,a33 が門松列である
つまり、タテ、ヨコ、ナナメ に行列の成分を見たとき、全て門松列になっていることが条件です。

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

入力

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

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

L
a11 a12 a13
a21 a22 a23
a31 a32 a33

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

出力

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

サンプル

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

a23=6,a32=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つ目のケースはa12=1,a32=2のパターンとa12=2,a32=1のパターンの2通りです。
あけましておめでとうございます。

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