問題一覧 > 通常問題

No.3345 Reducible Sequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 33
作問者 : MZKi / テスター : tassei903 jupiter_68 noya2
ProblemId : 9334 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-11-13 17:50:54
コンテストの他の問題:

問題文

正の整数からなる長さ $N$ の数列 $A$ が与えられます。

$A$ から添字の重複を許さずいくつかの要素を選び、それらを並び替えて以下の条件を満たすよう新しい数列 $B$ を作るとき、$B$ の長さの最大値を求めてください。

  • $B$ の長さを $M$ として、任意の $i\ (1 \leq i \leq M)$ について $B_i$ は $i$ の倍数である。

入力

$N$
$A_1\ A_2\ \dots\ A_N$

  • $1 \le N \le 5000$
  • $1 \le A_i \le 5000\ (1 \le i \le N)$
  • 入力は全て整数である。

出力

$B$ の長さの最大値を出力し、最後に改行してください。

サンプル

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

$B = (1,4,3)$ が長さ $3$ で、これが最も長いです。

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

$B = (1,2,3,4)$ が長さ $4$ で、これが最も長いです。最長となる $B$ が $A$ と等しいこともあります。

サンプル3
入力
12
2 71 43 80 37 42 61 2 40 22 93 89
出力
6

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