Under construction

Still being built. Things may change

A Random Problem

Time limit2sMemory limit512 MB

Summary
Given p random digits, find a triple correlation a(n)b(m)c that satisfies all three rules and occurs at least ceil(p/40)+1 times, or report random sequence.
Level

Medium5 of 10

Topics
String, Brute force, Implementation
Solved
No attempts yet

Statement

Generating a random number sequence is not easy. Many sequences may look random, but a closer look can reveal hidden regularities in how the numbers occur. For example, consider the following 100-digit "random" sequence starting with 4 7 9...:

4 7 9 5 9 3 5 0 0 1 7 8 5 0 2 6 3 5 4 4
4 6 3 3 2 7 1 8 7 8 7 6 1 1 7 2 5 4 7 2
0 4 4 5 8 3 0 6 9 3 2 6 6 8 5 2 5 1 2 7
2 4 1 0 0 4 9 1 8 7 5 0 4 4 8 4 3 2 6 8
8 5 6 7 0 9 7 0 3 6 1 4 4 1 2 3 2 6 9 9

Whenever a 4 is followed immediately by another 4, the third value after this is a 3. We call features like this triple correlations and write them as 4(1)4(3)3, where the numbers in parentheses give the distance between each pair of values. More precisely, a sequence of p digits has an a(n)b(m)c triple correlation if:

  1. any time there is an a followed n locations later by a b, there is always a c located m locations after the b, unless b's location is within distance m - 1 of the end of the sequence.
  2. any time there is a b followed m locations later by a c, there is always an a located n locations before the b, unless b's location is within distance n - 1 of the beginning of the sequence.
  3. any time there is an a followed n + m locations later by a c, there is always a b located n locations after the a.
  4. the correlation occurs at least ceil(p/40) + 1 times, where ceil(x) is the smallest integer greater than or equal to x.

Input

Input starts with a positive integer p (p ≤ 1 000), the number of random digits in the sequence. The p digits follow on the next lines, separated by spaces and possibly spread across multiple lines. No line contains more than 100 digits, and there are no blank lines.

Output

Print triple correlation a(n)b(m)c found if such a correlation occurs in the list, with a, b, c, n, and m filled in. Otherwise, print the phrase random sequence. If several triple correlations occur, print the one whose first occurrence (determined by the first occurrence of its a-value) is earliest in the sequence. If there is still a tie, choose the one with the smaller n, and if there is still a tie, the one with the smaller m.

Examples2

  1. Example 1

    Input
    100
    4 7 9 5 9 3 5 0 0 1 7 8 5 0 2 6 3 5 4 4
    4 6 3 3 2 7 1 8 7 8 7 6 1 1 7 2 5 4 7 2
    0 4 4 5 8 3 0 6 9 3 2 6 6 8 5 2 5 1 2 7
    2 4 1 0 0 4 9 1 8 7 5 0 4 4 8 4 3 2 6 8
    8 5 6 7 0 9 7 0 3 6 1 4 4 1 2 3 2 6 9 9
    
    Expected output
    triple correlation 4(1)4(3)3 found
    
  2. Example 2

    Input
    10
    1 2 3 1 2 2 1 1 3 0
    
    Expected output
    random sequence