2011 Canadian Computing Competition, Stage 1

Problem J3: Sumac Sequences

In a sumac sequence, t₁, t₂, …, t_m, each term is an integer greater than or equal to 0. Also, each term, starting with the third, is the difference of the preceding two terms (that is, t_n+2 = t_n − t_n+1 for n ≥ 1). The sequence terminates at t_m if t_m−1 < t_m.

For example, if we have 120 and 71, then the sumac sequence generated is as follows:

120, 71, 49, 22, 27

This is a sumac sequence of length 5.

Input Format

The input will be two positive integers t₁ and t₂ (0 < t₂ < t₁ < 10000).

Output Format

The output will be the length of the sumac sequence given by the starting numbers t₁ and t₂.

Sample Input

120
71

Sample Output

5

All Submissions
Best Solutions

Point Value: 5
Time Limit: 2.00s
Memory Limit: 16M
Added: Mar 01, 2011

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

so difficult!who can help me???

why you  think it's difficult when you already finished it??????????????????????

Should the runtime be changed to 2 seconds and memory 16M?

I went through and lowered a bunch of time and memory constraints, but I left a lot untouched. These constraints don't really matter if they're higher than necessary, though.