blackbee4   1년 전

판도라의 부유 산들은 그 구조가 어떻게 존재할 수 있는지 이해하려는 인간 과학자들, 특히 지질학자와 물리학자들에게 도전 과제를 제시하고 있습니다.

산들을 탐사하던 중, 과학자들은 흥미로운 겹쳐진 부유 산 구조를 우연히 발견했습니다. 이 구조에서는 더 큰 산이 스택의 더 높은 곳에 위치하며, 서로 다른 산들이 포개져 쌓여 있는 것처럼 보였습니다.

과학자들은 각 산의 크기를 계산할 수 있었고, 흥미로운 관찰 결과를 얻었습니다. 바로 산들의 크기가 (일반화된) 피보나치 수열을 형성한다는 것입니다.

수열 x1, x2, ..., xn은 모든 i > 2에 대해 다음을 만족할 경우 일반화된 피보나치 수열(generalized Fibbonacci sequence)이라고 불립니다.

xi = x{i-1} + x{i-2}

표준 피보나치 수열은 단순히 x1 = 1, x2 = 1인 일반화된 피보나치 수열입니다.

일반화된 피보나치 수열의 예시는 다음과 같습니다: 2, 5, 7, 12, 19, ...

당신의 목표는 이 추측을 검증하는 과학자들을 돕는 것입니다. 구체적으로, 당신은 주어진 수열이 일반화된 피보나치 수열인지 아닌지를 결정하는 프로그램을 작성해야 합니다.

입력

테스트 데이터 파일의 첫 번째 줄에는 테스트 케이스의 수 n이 포함됩니다.

그 후, 각 줄에는 하나의 테스트 케이스가 포함됩니다.

테스트 케이스는 수열의 요소 개수 k로 시작하며, 그 뒤에 수열을 구성하는 k개의 숫자가 나옵니다.

모든 숫자는 0 이상이고 2^30 미만이라고 가정합니다.

출력

각 테스트 케이스에 대해, 수열이 일반화된 피보나치 수열이면 "YES"를, 아니면 "NO"를 출력해야 합니다.

댓글을 작성하려면 로그인해야 합니다.