CCC '11 J3 - Sumac Sequences - Olympiads Online Judge

CCC '11 J3 - Sumac Sequences

View as PDF

Submit solution

All submissions

Best submissions

Points: 5 (partial)

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$ ~t_1, t_2, \dots, t_m~, each term is an integer greater than or equal $0$ ~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}$ ~t_{n+2} = t_n - t_{n+1}~ for $n \ge 1$ ~n \ge 1~). The sequence terminates at $t_m$ ~t_m~ if $t_{m-1} < t_m$ ~t_{m-1} < t_m~.

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

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

This is a sumac sequence of length $5$ ~5~.

Input Specification

The input will be two positive numbers $t_1$ ~t_1~ and $t_2$ ~t_2~, with $0 < t_2 < t_1 < 10\,000$ ~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$ ~t_1~ and $t_2$ ~t_2~.

Sample Input

120
71

Output for Sample Input

Comments

-3

powerroy commented on Oct. 21, 2025, 7:27 a.m.

... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...

-1

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

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

-1

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

it's just this question

20

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

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

-2

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 :(

-1

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

3

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

Smaller or equal to for ppl who got 4 wrong

2

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.

16

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

-1

MCRedstoneEnginnerHuanYin commented on Feb. 16, 2020, 1:56 p.m. ← edit 2 →

Thanks. I've meet the same question and this text helps me alot.

7

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.

22

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

Thank you! Merry Christmas :)