No.3345 Reducible Sequence
タグ : / 解いたユーザー数 36
作問者 :
MZKi
/ テスター :
noya2
Problem Statement
You are given a sequence $A$ of length $N$ consisting of positive integers.
Choose some elements from $A$ without choosing the same index more than once, and rearrange them to form a new sequence $B$ satisfying the following condition. Find the maximum possible length of $B$.
- Let $M$ be the length of $B$. For every $i\ (1 \leq i \leq M)$, $B_i$ is a multiple of $i$.
Input
$N$ $A_1\ A_2\ \dots\ A_N$
- $1 \le N \le 5000$
- $1 \le A_i \le 5000\ (1 \le i \le N)$
- All inputs are integers.
Output
Output the maximum possible length of $B$, followed by a newline.
Sample
Sample 1
Input
4 1 5 3 4
Output
3
$B = (1,4,3)$ has length $3$, and this is the longest.
Sample 2
Input
4 1 2 3 4
Output
4
$B = (1,2,3,4)$ has length $4$, and this is the longest. The longest $B$ may be equal to $A$.
Sample 3
Input
12 2 71 43 80 37 42 61 2 40 22 93 89
Output
6
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。