First of all, a happy new year to all of you
Now, here is program which should be tried by junior as well as senior programmers(though they might too busy even to visit the site)
This problem is about sequences of positive integers a1,a2,…,aN.
A subsequence of a sequence is anything obtained by dropping some
of the elements. For example, 3,7,11,3 is a subsequence of
6,3,11,5,7,4,3,11,5,3 , but 3,3,7 is not a subsequence of
6,3,11,5,7,4,3,11,5,3 .
A fully dividing sequence is a sequence a1,a2,…,aN where ai divides aj whenever i < j. For example, 3,15,60,720 is a fully dividing
sequence.
Given a sequence of integers your aim is to find the length of the
longest fully dividing subsequence of this sequence.
Consider the sequence 2,11,16,12,36,60,71,17,29,144,288,129,432,993 .
It has two fully dividing subsequences of length 5,
2,11,16,12,36,60,71,17,29,144,288,129,432,993 and
2,11,16,12,36,60,71,17,29,144,288,129,432,993
and none of length 6 or greater.
Input format
The first line of input contains a single positive integer
N indicating the length of the input sequence. Lines 2,…,N+1
contain one integer each. The integer on line i+1 is ai.
Output format
Your output should consist of a single integer indicating
the length of the longest fully dividing subsequence of
the input sequence.
Test Data
You may assume that N = 10000.
Example:
Here are the inputs and outputs corresponding to the two examples
discussed above.
Sample input 1:
9
2
3
7
8
14
39
145
76
320
Sample output 1:
3
Sample input 2:
5
2
4
6
18
54
Sample output 2:
4
For test data and hints send me an email at [email protected].
—————————————————————–
PS:I have test data which contain as many as 10000 numbers. To check
my program for these large inputs , I need to read them directly
from the *.dat files(i bet nobody can type 10000 nos) .
Can somebody tell me how to do this???