A Random Problem
Time limit2sMemory limit512 MB
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:
- 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.
- 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.
- 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.
- 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.