### 2011 Canadian Computing Competition, Stage 1

## Problem J3: Sumac Sequences

In a sumac sequence, `t`_{1}, `t`_{2}, …, `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`if

_{m}`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`_{1} and `t`_{2} (0 < `t`_{2} < `t`_{1} < 10000).

### Output Format

The output will be the length of the sumac sequence given by the starting numbers `t`_{1} and `t`_{2}.

### 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)

Kiritoon Nov 17, 2015 - 12:49:53 am UTC Runtime and Memory Constraintsjargonon Nov 17, 2015 - 2:19:45 am UTC Re: Runtime and Memory Constraints