CCC '11 J3 - Sumac Sequences

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Canadian Computing Competition: 2011 Stage 1, Junior #3

In a sumac sequence, t_1, t_2, \dots, t_m, each term is an integer greater than or equal 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 \ge 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:

\displaystyle  120, 71, 49, 22, 27.

This is a sumac sequence of length 5.

Input Specification

The input will be two positive numbers t_1 and t_2, with 0 < t_2 < t_1 < 10\,000.

Output Specification

The output will be the length of the sumac sequence given by the starting numbers t_1 and t_2.

Sample Input


Output for Sample Input



  • 1
    Shadow_Walker  commented on Nov. 20, 2019, 1:01 a.m. edited

    For some reason my code can't solve test case 4. can someone help me with it(btw I'm using java).

    Edit:nvm i fixed it

    • -1
      YiJnC  commented on Dec. 4, 2019, 11:35 p.m.

      Could you tell me how you fixed it? I'm also using java and stuck here

  • 3
    sankeeth_ganeswaran  commented on Jan. 5, 2019, 7:05 p.m.

    Can someone help me with my code, I failed test case 4. Thanks.

    • 6
      JustinXu  commented on Jan. 5, 2019, 9:16 p.m. edit 4

      sankeeth_ganeswaran. I believe there is a minor error in your code. As a reference, try:

      610 and 377

      Output should be 17, and not 15

      Edit: Hint, this can be done recursively and iteratively

  • 5
    raytonlin1  commented on Dec. 24, 2017, 1:18 p.m.

    IDK what my python 2 code did wrong, why is test case 4 incorrect

    • 4
      jkguipqnjcy49979693  commented on Dec. 24, 2017, 1:24 p.m.

      Your while loop condition is ignoring a key case... compare the "termination condition" in the problem statement to when your loop terminates.

      • 5
        raytonlin1  commented on Jan. 10, 2019, 8:46 p.m.

        Thank you! Merry Christmas :)