CCC '10 J4 - Global Warming

View as PDF
Submit solution
Points: 5 (partial)
Time limit: 1.0s
Memory limit: 256M
Problem type
Canadian Computing Competition: 2010 Stage 1, Junior #4

Your task is to help scientists predict the trend of global warming. One of the hypotheses they are considering is that over long periods of time, the average temperature follows certain cycles, but each time the cycle starts from a higher temperature level. The temperatures are measured over five-year averages, and expressed in tenths of a degree.

For example, if the following five-year averages are observed:

\displaystyle 3, 4, 6, 4, 5, 7, 5

then we can calculate that the temperature changes first 1 up, then 2 up, then 2 down, 1 up, 2 up, and 2 down. There is a cycle of changes of length three which covers all of the temperature differences: (+1, +2, -2). In other words, if we look at the differences starting at the first position, there is a cycle of length three of the form (+1, +2, -2) followed by another cycle of length three of exactly the same form. By way of another example, suppose the following average temperatures are observed:

\displaystyle 3, 4, 6, 7.

In this case, there is a difference of one up, two up, then one up. We would consider the shortest cycle to be length two in this case: the cycle (+1, +2). Notice that this cycle occurs once, followed by one truncated occurrence of exactly the same cycle.

Your task is to find the shortest such cycle from a given sequence of temperatures.

Input Specification

The input consists of a number of test cases. Each test case starts with the number n (1 \le n \le 20), representing the number of temperatures in a sequence, followed by the sequence of n temperatures. You may assume that each temperature input is an integer in the range -1000 \dots 1000 inclusive. The numbers are separated by a single space. The last test case is indicated by a zero and should produce no output.

Output Specification

For each test case, produce the length of the shortest temperature cycle. The cycle always exists, since the whole sequence could be treated as one long cycle.

Sample Input

7 3 4 6 4 5 7 5
3 1 3 5
3 1 4 5
4 3 4 6 7
0

Sample Output

3
1
2
2

Comments


  • -2
    Payne  commented on Nov. 11, 2022, 3:06 a.m.

    shouldn't the maximum number of test cases be mentioned?


    • -11
      volcano  commented on Nov. 12, 2022, 4:43 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • 9
    Evanhyd  commented on March 6, 2021, 9:09 p.m.

    tips: the answer for 6 1 3 6 8 11 16 would be 5 instead of 2


  • 15
    bariumlanthanum  commented on May 31, 2020, 1:44 p.m. ← edit 2

    this problem will be renamed to find the shortest repeating sequence after Elon Musk stops global warming


  • -1
    jerry0101  commented on Jan. 9, 2020, 3:54 p.m.

    how does 3 1 4 5 give 2

    its a diff of 3 and 1


    • 7
      Max01110  commented on Feb. 16, 2020, 3:33 a.m.

      yes, the difference is 3 and 1. Therefore there is only one cycle. Its length is 2.


    • 7
      p1geon  commented on Jan. 9, 2020, 4:55 p.m.

      The cycle always exists, since the whole sequence could be treated as one long cycle.


  • 2
    Togohogo1  commented on Dec. 18, 2019, 3:41 p.m.

    Would this input: 8 3 4 6 4 5 7 5 6

    Output this: 3


    • 0
      ChrisLi  commented on Jan. 7, 2020, 4:34 p.m.

      YES.


  • -2
    TingHoMarcus  commented on Feb. 19, 2019, 4:34 a.m.

    [3, 1, 4, 5] how does this give 2????


    • 24
      p1geon  commented on Feb. 19, 2019, 1:37 p.m.

      The first number isn't a term in the pattern, it denotes the amount of terms in the sequence.


  • 80
    kobortor  commented on Jan. 25, 2015, 1:50 a.m. ← edited

    If there is a sequence with length 1, the cycle is length 0