問題一覧 > 通常問題

No.390 最長の数列

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 284
作問者 : ぴろずぴろず / テスター : 37zigen37zigen
19 ProblemId : 486 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-06-25 01:46:32

問題文

$N$個の正の整数を含む空でない集合$S= \{ x_1,x_2, \dots ,x_N \}$が与えられます。
$S$に対して、次の$2$つの性質をもつ長さ$M(\geq 1)$の数列$(a_1,a_2, \dots ,a_M)$を「良い」数列と言うことにします。

  1. 任意の$i(1 \leq i \leq M)$に対して$a_i \in S$
  2. 任意の$i(1 \leq i \leq M - 1)$に対して、$a_i < a_{i+1}$かつ$a_{i+1}$ は $a_i$ の倍数

最も長い「良い」数列の長さを求めるプログラムを作成してください。

入力

$N$
$x_1$ $x_2$ $\dots$ $x_N$

$1$行目に$N$が与えられます。
$2$行目にスペース区切りで$N$個の整数$x_1,x_2, \dots ,x_N$が与えられます。

$1 \leq N \leq 10^5$
$1 \leq x_i \leq 10^6 \; (1 \leq i \leq N)$
$x_i \neq x_j \; (1 \leq i < j \leq N)$

出力

最も長い「良い」数列の長さを$1$行に出力してください。 最後に改行してください。

サンプル

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

「良い」数列として、$(1,2)$や$(2,4)$や$(5)$などが考えられます。
長さが$3$の「良い」数列は$(1,2,4)$のみで、これが最大値です。

サンプル2
入力
7
3 4 8 9 16 27 432
出力
4

長さが最大となる「良い」数列は$(3,9,27,432)$と$(4,8,16,432)$の$2$つあります。
「良い」数列の長さの最大を出力するので、$4$を出力します。

サンプル3
入力
7
1 2 22 88 8 4 440
出力
6

$x_1, x_2, \dots x_N$は昇順に並んでいないこともあります。

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

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