問題一覧 > 通常問題

No.2178 Payable Magic Items

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 68
作問者 : MasKoaTSMasKoaTS / テスター : mine691mine691 potato167potato167
4 ProblemId : 8311 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-11-28 21:07:24

問題文

魔法使いのコアさんは、$1,2,\dots,N$ の番号が付いた $N$ 個の魔道具を作りました。

各魔道具には性能を表す $K$ 個の値が設定されており、魔道具 $i$ $(1 \leq i \leq N)$ の $j$ $(1 \leq j \leq K)$ 番目の値は $S_{i,j}$ です。

コアさんは、これらの魔道具の保管にかかる費用をなるべく小さく抑えたいので、
次の条件を満たす魔道具 $x$ $(1 \leq x \leq N)$ をすべて売却することにしました。

  • $\boldsymbol{x}$ と異なるある整数 $y$ $(1 \leq y \leq N)$ が存在し、任意の整数 $k$ $(1 \leq k \leq K)$ に対して $S_{x,k} \leq S_{y,k}$ が成り立つ。

このとき、コアさんが売却する魔道具の個数を求めてください。

制約

  • $1 \leq N \leq \min(2 \times 10^{5}, 5^{K})$

  • $1 \leq K \leq 8$

  • $0 \leq S_{i,j} \leq 4$ $(1 \leq i \leq N \text{ かつ } 1 \leq j \leq K)$

  • $( S_{i,1}, S_{i,2}, \dots, S_{i,K} ) \neq ( S_{j,1}, S_{j,2}, \dots, S_{j,K} )$ $(1 \leq i < j \leq N)$

  • $N, K$ 及び $S_{i,j}$ $(1 \leq i \leq N \text{ かつ } 1 \leq j \leq K)$ はすべて整数

入力

入力は次の形式で与えられます。

$N$ $K$
$S_{1,1} S_{1,2} \cdots S_{1,K}$
$S_{2,1} S_{2,2} \cdots S_{2,K}$
 $\vdots$    $\ddots$    $\vdots$
$S_{N,1} S_{N,2} \cdots S_{N,K}$
  • $1$ 行目には $N, K$ がこの順に半角スペース区切りで与えられる

  • $(1 + i)$ $(1 \leq i \leq N)$ 行目には $S_{i,1}, S_{i,2} \dots, S_{i,K}$ がこの順に長さ $K$ の文字列として与えられる

出力

答えを $1$ 行に出力してください。

サンプル

サンプル1
入力
3 3
210
420
004
出力
1

コアさんが売却するのは魔道具 $1$ のみです。

例えば、魔道具 $1$ と魔道具 $2$ の性能を比較したとき、
任意の整数 $k$ $(1 \leq k \leq 3)$ に対して $S_{1,k} \leq S_{2,k}$ が成り立ちます。

また、魔道具 $1$ と魔道具 $3$ の性能を比較したとき、$S_{3,1} \leq S_{1,1}$ 及び $S_{3,2} \leq S_{1,2}$ は成り立ちますが、
$S_{3,3} > S_{1,3}$ であるため、魔道具 $3$ は売却されません。

サンプル2
入力
2 2
40
04
出力
0

コアさんが売却する魔道具はありません。

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

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