首页 > ACM题库 > HDU-杭电 > hdu 3381 Floating Mountain Stability待解决[解题报告]C++
2014
03-16

hdu 3381 Floating Mountain Stability待解决[解题报告]C++

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 >- 230 and < 230.

输出:

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 >- 230 and < 230.

样例输入:

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


  1. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish