問題一覧 > 通常問題

No.390 最長の数列

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

問題文

N個の正の整数を含む空でない集合S={x1,x2,,xN}が与えられます。
Sに対して、次の2つの性質をもつ長さM(1)の数列(a1,a2,,aM)を「良い」数列と言うことにします。

  1. 任意のi(1iM)に対してaiS
  2. 任意のi(1iM1)に対して、ai<ai+1かつai+1ai の倍数

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

入力

N
x1 x2  xN

1行目にNが与えられます。
2行目にスペース区切りでN個の整数x1,x2,,xNが与えられます。

1N105
1xi106(1iN)
xixj(1i<jN)

出力

最も長い「良い」数列の長さを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

x1,x2,xNは昇順に並んでいないこともあります。

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

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