DivInts
You are given a set A of N integers from the interval [1, 100 000 000]. You have to find the longest sequence a made of the numbers from A such that for every two adjacent elements \mathbf{a_i} and \mathbf{a_j} (i = j – 1) we have \mathbf{a_j} to be divisible by \mathbf{a_i}. If there are multiple longest sequences, you have to find the one that is lexicographically smallest.
For two sequences \math{X = (x_1, x_2, ..., x_n)} and \math{Y = (y_1, y_2, ..., y_n)} we have X to be lexicographically smaller than Y if there exist i, such that:
1. for all j < i we have \mathbf{x_j = y_j}
2. \mathbf{x_i < y_i}.
InputFrom the first line of the standard input read an integer N (2 \leq N \leq 1 000). From the next N lines read the numbers from A
The input will always contain two number from A (\mathbf{A_i} and \mathbf{A_j}) such that \mathbf{A_i} is divisible by \mathbf{A_j}.
The input will always contain two number from A (\mathbf{A_i} and \mathbf{A_j}) such that \mathbf{A_i} is divisible by \mathbf{A_j}.
Outputto the first line of the standard output write an integer M, where M is the length of the longest sequence that meets the requirements described above. To the second line output M numbers of the sequence separated by a single space. The second line should contain exactly M-1 spaces - you should not output a space before the first number or after the last number.
Input:
Output:
20
8
2
5
3
18
19
4
11
10
9
2
17
15
14
20
10
5
13
12
14Output:
5
2 2 10 10 20
Input:
Output:
6
1
3
5
7
11
13Output:
2
1 3
Explanation:
There are 5 sequences with the length 2 that satisfy the conditions:
(1, 3), (1, 5), (1, 7), (1, 11), (1, 13).
The lexicographically smallest is (1, 3).
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.