CCC '11 J3 - Sumac Sequences

View as PDF
Submit solution
Points: 5
Time limit: 2.0s
Memory limit: 256M
Problem type
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

120
71

Output for Sample Input

5

Comments


  • 1
    ryanlica2009  commented on Jan. 9, 2023, 1:40 a.m.

    Why does this year feel so much easier than the rest lol


    • 0
      yihanhu888  commented on Jan. 13, 2023, 5:00 a.m.

      it's just this question


  • 16
    Tommy_Shan  commented on Aug. 28, 2021, 3:26 p.m.

    Test case 4: 610 377 Note: equal or bigger instead of bigger


    • 0
      savirsingh  commented on July 27, 2022, 10:03 p.m.

      I didn't need to use equal or bigger and I didn't run into any problems either. https://dmoj.ca/submission/4727992

      Idk why so many people are failing test 4 :(


      • 0
        960t  commented on Nov. 5, 2022, 12:01 a.m. ← edit 7

        (sorry for the ton of edits, correct me if I'm stupid)

        probably because you used the smaller than operator for comparing the second last number to the last number:

        (a = sumaclist[-2] - sumaclist[-1]), and (if sumaclist[-1] < a:)

        detecting if the sumac number was found.

        other people made their code repeat if the number wasn't found, so they had to use the >= sign between the numbers instead


  • 2
    justinjiang37  commented on Feb. 15, 2021, 11:33 p.m.

    Smaller or equal to for ppl who got 4 wrong


    • 3
      rasput  commented on July 17, 2021, 8:31 a.m.

      Thanks)


  • 4
    sankeeth_ganeswaran  commented on Jan. 6, 2019, 12:05 a.m.

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


    • 17
      JustinXu  commented on Jan. 6, 2019, 2:16 a.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


  • 6
    raytonlin1  commented on Dec. 24, 2017, 6:18 p.m. ← edited

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


    • 9
      jkguipqnjcy49979693  commented on Dec. 24, 2017, 6: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.


      • 19
        raytonlin1  commented on Jan. 11, 2019, 1:46 a.m.

        Thank you! Merry Christmas :)