No.497 入れ子の箱

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 73
作問者 : tailstails / テスター : confconf

2 ProblemId : 488 / 出題時の順位表

問題文

$N$ 個の直方体の箱があります。サイズは様々です。
これらの箱の中からいくつかを選び出して、マトリョーシカのように、小さい箱を大きい箱の中に入れることを繰り返して、入れ子の箱を作ろうとしています。
さて、最大で何重の入れ子にすることができますか?

なお、
箱は向きを変えたり横倒しにしたりして用いても構いません。
(任意に向きを変えたり横倒しにしたりした後の)箱 $i$ の幅,奥行き,高さが、箱 $j$ の幅,奥行き,高さよりもそれぞれ真に小さい場合に限り、箱 $i$ を箱 $j$ の中に入れることができます。
1つの箱の中に直接2つの箱を入れても、それは3重ではありません。

入力

$N$
$X_1$ $Y_1$ $Z_1$
$X_2$ $Y_2$ $Z_2$
$\vdots$
$X_N$ $Y_N$ $Z_N$

$1 \le N \le 1000$
$1 \le X_i,Y_i,Z_i \lt 10^8$

$N, X_i, Y_i, Z_i$ はいずれも整数です。
箱の数は $N$ 個です。
$i$ 番目の箱のサイズは、三辺の長さがそれぞれ $X_i, Y_i, Z_i$ です。

出力

箱を最大で何重の入れ子にすることができるか、その答えを整数で出力してください。
箱を全く入れ子にできない場合は、 $1$ を出力してください。

サンプル

サンプル1
入力
4
2 2 2
1 1 1
3 3 3
4 1 4
出力
3

下図のように、サイズ $(1,1,1)$ の箱をサイズ $(2,2,2)$ の箱の中に入れ、
それをサイズ $(3,3,3)$ の箱の中に入れれば、3重にすることができます。
サイズ $(4,1,4)$ の箱は用いませんでした。
(「サイズ $(X,Y,Z)$ の箱」とは、三辺の長さがそれぞれ $X, Y, Z$ の箱の意味です。)

※ 図は高さの表現を省略しています。

サンプル2
入力
2
1 1 3
2 4 2
出力
2

サイズ $(1,1,3)$ の箱を横倒しにすれば、サイズ $(2,4,2)$ の箱の中に入れることができます。

サンプル3
入力
2
5 5 3
4 3 3
出力
1

それぞれの箱をどのような向きにしても、一方の箱の中にもう一方の箱を入れることができません。
全く入れ子にすることができないので、答えは $1$ になります。

提出ページヘ