(cache)B - Kagami Mochi

コンテスト時間: 2018-01-07(日) 12:00 ~ 2018-01-07(日) 13:40 (100分) AtCoderホームへ戻る

B - Kagami Mochi 解説

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : $200$ 点

問題文

$X$ 段重ねの鏡餅 $(X \geq 1)$ とは、 $X$ 枚の円形の餅を縦に積み重ねたものであって、どの餅もその真下の餅より直径が小さい（一番下の餅を除く）もののことです。例えば、直径 $10$ 、 $8$ 、 $6$ センチメートルの餅をこの順に下から積み重ねると $3$ 段重ねの鏡餅になり、餅を一枚だけ置くと $1$ 段重ねの鏡餅になります。

ダックスフンドのルンルンは $N$ 枚の円形の餅を持っていて、そのうち $i$ 枚目の餅の直径は $d_{i}$ センチメートルです。これらの餅のうち一部または全部を使って鏡餅を作るとき、最大で何段重ねの鏡餅を作ることができるでしょうか。

制約

$1 \leq N \leq 100$
$1 \leq d_{i} \leq 100$
入力値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $d_{1}$ 
 $:$ 
 $d_{N}$

出力

作ることのできる鏡餅の最大の段数を出力せよ。

入力例 1 Copy

Copy

出力例 1 Copy

Copy

直径 $10$ 、 $8$ 、 $6$ センチメートルの餅をこの順に下から積み重ねると $3$ 段重ねの鏡餅になり、これが最大です。

入力例 2 Copy

Copy

出力例 2 Copy

Copy

すべての餅の直径が同じときは、 $1$ 段重ねの鏡餅しか作れません。

入力例 3 Copy

Copy

出力例 3 Copy

Copy

Score : points

An -layered kagami mochi is a pile of round mochi (rice cake) stacked vertically where each mochi (except the bottom one) has a smaller diameter than that of the mochi directly below it. For example, if you stack three mochi with diameters of , and centimeters from bottom to top in this order, you have a -layered kagami mochi; if you put just one mochi, you have a -layered kagami mochi.

Lunlun the dachshund has round mochi, and the diameter of the -th mochi is centimeters. When we make a kagami mochi using some or all of them, at most how many layers can our kagami mochi have?

If we stack the mochi with diameters of , and centimeters from bottom to top in this order, we have a -layered kagami mochi, which is the maximum number of layers.

When all the mochi have the same diameter, we can only have a -layered kagami mochi.