## 11582 - Colossal Fibonacci Numbers!

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

### 11582 - Colossal Fibonacci Numbers!

I get Wrong answer
here is mycode :

Code: Select all

``````Accepted
``````
Last edited by vahid sanei on Tue Dec 29, 2009 9:05 am, edited 1 time in total.
Impossible says I`m possible

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### Re: 11582 - Colossal Fibonacci Numbers!

Check the case.

Input:

Code: Select all

``126 121 111``
Output:

Code: Select all

``33``
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

### Re: 11582 - Colossal Fibonacci Numbers!

i got accepted by a lame method.
How did you find the period ? Found on net that period has to be less than 6*n. So generated upton 12*n and checked for repetition of first 10 numbers.
Anyone used floyd.

vahid, you are doing it wrong. a^b %n != a^b % p where p is the period, it could be within p<=6*n, source wikipedia

vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

### Re: 11582 - Colossal Fibonacci Numbers!

thanks Jan but i dont have idea for solving that
could u give me some hints ?
Impossible says I`m possible

vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

### Re: 11582 - Colossal Fibonacci Numbers!

Thanks tryit , i try it
Impossible says I`m possible

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Re: 11582 - Colossal Fibonacci Numbers!

tryit1 wrote:i got accepted by a lame method.
How did you find the period ? Found on net that period has to be less than 6*n. So generated upton 12*n and checked for repetition of first 10 numbers.
Anyone used floyd.
It seems the the series returns back to 0 1 1 ... for every value of n.
I didn't know about the 6*n figure, so I just kept on inserting new values until a 0 is followed by 1.

tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

### Re: 11582 - Colossal Fibonacci Numbers!

Yes it returns backs to 0 1 1 .. But that observation can mislead. From your AC solution looks like it doesn't in this case.

If we are given a sequence of numbers like 0,1,1,2,3,5,6,7,0,1,1,2,0,1,1,2,3,5,6,7,0,1,1,2

how do you find the period of this ? Any thing easier than KMP.

If the values were unique could we apply floyd cycle finding. Can we modify it for the above sequence ? i tried but when there are duplicate values it breaks.

I guess there should be some algorithm which finds the period of a repeating sequence much easily.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### Re: 11582 - Colossal Fibonacci Numbers!

tryit1 wrote:Yes it returns backs to 0 1 1 .. But that observation can mislead. From your AC solution looks like it doesn't in this case.

If we are given a sequence of numbers like 0,1,1,2,3,5,6,7,0,1,1,2,0,1,1,2,3,5,6,7,0,1,1,2

how do you find the period of this ? Any thing easier than KMP.

If the values were unique could we apply floyd cycle finding. Can we modify it for the above sequence ? i tried but when there are duplicate values it breaks.

I guess there should be some algorithm which finds the period of a repeating sequence much easily.
I haven't understood fully. Its a Fibonacci sequence. So, you cant find a sequence that you have mentioned. However, suppose the sequence is based on any other criteria. Then stl map (or a bst) is a solution to your problem, too. Of course if the number of states is small.
Ami ekhono shopno dekhi...
HomePage

tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

### Re: 11582 - Colossal Fibonacci Numbers!

You and sohel are right. It is a fibonacci sequence , so a first occurance of 0,1 starting with index > 2 solves the problem..My bad