Preparing NOJ

Mountains of Pandora

1000ms 65536K


The floating mountains of Pandora present a challenge for the human scientists, especially geologists

and physicists, who have been trying to understand how such structures could exist. While exploring

the mountains, the scientists stumbled across interesting stacked floating mountain structures, where

different mountains appeared stacked above one other, with the larger mountains being higher up in

the stack. The scientists were able to calculate the size of each mountain, and they made an interesting

observation: that the sizes of the mountains formed a (generalized) Fibbonacci sequence.

A sequence of numbers: x1, x2, ..., xn, is called a generalized Fibbonacci sequence if, for all i > 2,

xi = xi−1 + xi−2

The standard Fibbonacci sequence is simply a generalized Fibbonacci sequence with x1 = x2 = 1.

An example of generalized Fibbonacci sequence is: 2, 5, 7, 12, 19, ...

Your goal is to help the scientists verify this conjecture. Specifically, you are to write a program

that, given a sequence of numbers, decides whether the sequence is a generalized Fibbonacci sequence

or not.


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, and then

we have k numbers which form the sequence. Assume all numbers are  0, and that the numbers are

all < 230.


For each test case, you are to output “YES” (if the sequence is a generalized Fibbonacci

sequence) or “NO” (if it is not).

Sample Input:

6 1 1 2 3 5 8
7 1 2 2 4 6 10 16
4 2 10 12 22

Sample Output:







Provider NOJ

Code NOJ1389


Submitted 1

Passed 1

AC Rate 100%

Date 04/20/2019 10:03:10


Nothing Yet