問題一覧 > 通常問題

No.497 入れ子の箱

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 136
作問者 : tails / テスター : conf
5 ProblemId : 488 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-08-27 16:10:34

問題文

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

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

入力

N
X1 Y1 Z1
X2 Y2 Z2
⋮
XN YN ZN

1≤N≤1000
1≤Xi,Yi,Zi<108

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

出力

箱を最大で何重の入れ子にすることができるか、その答えを整数で出力してください。
箱を全く入れ子にできない場合は、 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 になります。

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