Here is the problem statement.
For solving this kind of problems we need to have a bit of noticing skills. Try to calculate the answer for n=1,2,3,4 by hand and you will easily notice the drill in here.Create a simple tree which will show the answer.
The tree shows the ways of creating numbers
When the length is 1 we can have 0 and 1 on our first position. When we are trying to form the sequence of length 2 we need to use the sequences we had already created and add 1 or 0 (if possible) to the end of the sequence. Obviously this is a problem of dynamic programming. Here is the table of answers from 1 to 4
1-2
2-3
3-5
4-8
We can easily notice that a[n]=a[n-1]+a[n-2]
The only problem we have in our task is the problem of constraints. N<=10000 obviously for N=10000 our answer will not fit in int64 I can say more the answer for N=10000 s 2009 digits long. We need to implement the long arithmetics. You can find information about that here.
No comments:
Post a Comment