問題一覧 > 通常問題

No.359 Kadomatsu Matrix

レベル : / AI推定難易度 : 1550 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 26
作問者 : koyumeishi / テスター : uwi
お気に入りにしたユーザー ProblemId : 940 / 自分の提出
問題文最終更新日: 2026-06-25 02:26:58
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 門松コンテスト (順位表) の他の問題:

Problem Statement

A Kadomatsu sequence is a sequence of $3$ elements $A_1, A_2, A_3$ that satisfies the following 2 conditions.

  • $A_1, A_2, A_3$ are all distinct
  • Among the $3$ elements, $A_2$ is the largest or $A_2$ is the smallest

A Kadomatsu matrix of order 3 is a square matrix of order 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)$ that satisfies all of the following conditions.

  • For every row of the matrix, the sequence $a_{r1}, a_{r2}, a_{r3}$ ($r=1,2,3$) is a Kadomatsu sequence
  • For every column of the matrix, the sequence $a_{1c}, a_{2c}, a_{3c}$ ($c=1,2,3$) is a Kadomatsu sequence
  • For the anti-diagonal of the matrix, the sequence $a_{13}, a_{22}, a_{31}$ is a Kadomatsu sequence
  • For the main diagonal of the matrix, the sequence $a_{11}, a_{22}, a_{33}$ is a Kadomatsu sequence
In other words, the condition is that the entries of the matrix form a Kadomatsu sequence whenever they are read vertically, horizontally, or diagonally.

Taro is trying to place $9$ pieces of bamboo in a $3 \times 3$ frame so that their lengths form a Kadomatsu matrix.
He has already placed $7$ pieces in the frame, but he was $2$ pieces short, so he cut $1$ piece of bamboo of length $L$ from the bamboo grove.
When this cut piece is split into $2$ parts and placed in the frame to complete a Kadomatsu matrix, tell Taro how many Kadomatsu matrices are possible.
However, fractions are considered bad luck, so the lengths of the bamboo pieces after splitting must be positive integers. Also, the bamboo is cut in the "zundo" (flat cut) style rather than the "sogi" (slanted cut) style (reference), so when it is split so that one part has length $x$, the other part has length $L-x$.

Input

All input values are given as integers.
$T$

The first line gives the number of test cases $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}$

The first line of each test case gives the length of the cut bamboo $L (1 \leq L \leq 10^9)$. The following 3 lines give the lengths of the bamboo placed in the frame $a_{ij} (0 \leq a_{ij} \leq 10^9)$.
When $a_{ij} = 0$, no bamboo has been placed there yet.
There are always exactly $2$ positions where no bamboo has been placed.

Output

For each test case, output on one line the number of possible Kadomatsu matrices.

Sample

Sample 1
Input
1
10
7 8 5
1 9 0
3 0 2
Output
1

There is 1 way: $a_{23} = 6, a_{32} = 4$.

Sample 2
Input
1
10
1 3 0
5 0 7
4 8 6
Output
0

It seems that no matter how hard you try, it cannot be made into a Kadomatsu matrix.

Sample 3
Input
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
Output
2
0
1
6

In the first case, there are 2 ways: the pattern with $a_{12} = 1, a_{32} = 2$ and the pattern with $a_{12} = 2, a_{32} = 1$.
Happy New Year!

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