Floating Mountain Stability

After receiving your program from Problem 1, the scientists used it to try to verify their conjecture (that the sizes of stacked floating mountains formed a generalized Fibbonacci sequence). However, although they were able to verify the conjecture for a large number of cases, they discovered that there were stacked structures that did not satisfy the property. Further, they also discovered that floating mountains may have negative weights (they conjecture that this has to do with some unique properties of “Unobtainium”).

The scientists now believe that the sizes of the stacked mountains did follow generalized Fibbonacci sequence property originally (when they were formed), but they believe that some of the mountains in the structures may have been destroyed or may have drifted apart. They further observed that at most 9 consecutive mountains in the stack may be removed without compromising the stability of the structure. They are now trying to verify this new conjecture.

You are to write a program for this purpose. Specifically, given a sequence of numbers, some of which may be negative, you must determine if the numbers are part of a generalized Fibbonacci sequence (let’s call it the original sequence), such that all consecutive pairs of numbers in the input sequence are less than 10 apart (i.e., fewer than 9 items between any consecutive pair of numbers) in the original generalized Fibbonacci sequence.

As an example, the sequence: 0 6 16, follows this property because the numbers are from the following generalized Fibbonacci sequence:
0 2 2 4 6 10 16
and 0 & 6 are only 4 numbers apart in the generalized sequence.

As another example: the sequence -22 8 77 125, also satisfies the property. Here is the corresponding generalized Fibbonacci sequence:
37 -22 15 -7 8 1 9 10 19 29 48 77 125

The first line in the test data file contains the number of test cases, n. After that, each line contains one test case. The test case begins with the number of elements in the sequence, k (k < 50), and then we have k numbers which form the sequence. Assume the numbers are all >- 2³⁰ and < 2³⁰.

For each test case, you are to output ”STABLE” (if the sequence satisfies the property) followed by the first five elements of the generalized Fibbonacci sequence (beginning with the first number in the input sequence), or ”UNSTABLE” (if it does not). If multiple generalized Fibbonacci sequences are possible, select the sequence with the smallest gap (i.e., number of missing numbers) between the first two numbers.

3
3 0 6 16
4 -22 8 77 125
4 1 1 1 1

STABLE 0 2 2 4 6
STABLE -22 15 -7 8 1
UNSTABLE

2010 MHSPC