Informatica Online Judge

  큐브러버 [1750 / 06D6]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 17   Total Tried : 50


The Champion of this Problem (C++) : gs16051 - ms / 313byte
My Best Submission (C++) : N/A

[2016 나는코더다 송년 대회 (German Collegiate Programming Contest 2010)]

Background

지학이는 3차 다항식(cubic polynomial)을 좋아하는 잘 알려진 cubelover 이다.

어느 화창한 봄날, 지학이는 아파트 놀이터에서 승현이가 길이 $n$의 정수 수열 $x_1, x_2, ..., x_n$ 을 가지고 노는 것을 보았다. 지학이는 그 아파트의 짱이었고, 승현이보다 45일이나 먼저 태어난 형이었다. 지학이는 승현이를 보자마자 갖고 놀던 수열을 빼앗아 갔다.

승현이는 그 자리에서 엉엉 울기 시작했고, 마음이 약해진 지학이는 승현이가 $1 <= i <= n$인 모든 정수 $i$에 대해 $x_i = ai^3 + bi^2 + ci + d$를 만족하는 실수 $a$, $b$, $c$, $d$ 를 찾으면 수열을 돌려주겠다고 약속했다. (사실 3차 다항식이라 $a ≠ 0$이어야 하긴 하는데, 지학이는 그 정도로 엄밀하게 굴고 싶진 않은 모양이다.)

간만에 학교를 나와 외출을 즐기고 있는 당신은, 울고 있는 승현이와 눈을 마주쳤다. 승현이는 여러분에게 곧장 달려와서, 빨리 그러한 실수 $a$, $b$, $c$, $d$ 를 찾아달라고 졸랐다. 당신은 과연 승현이의 눈물을 닦아 줄 수 있는가?

Input

이 문제는 한 입력에 여러 개의 테스트 케이스가 주어진다. 첫번째 줄에 그러한 테스트 케이스의 개수 $T$ ($1 <= T <=1000$) 가 주어진다.

이후 $T$개의 줄이 주어진다. 첫번째로 수열의 길이인 정수 $n$ ($1 <=n <=500$) 이 주어진다. 이후 $n$ 개의 정수가 주어진다. 이 중 $i$번째 정수는 $x_i$ ($0 <=x_i <=50,000,000$) 를 뜻한다.

Output

$T$개의 줄에 걸쳐, 만약에 승현이가 원하는 실수 $a$, $b$, $c$, $d$가 존재한다면 YES, 존재하지 않는다면 NO를 출력한다.

IO Example

입력
3
1 3
5 0 1 2 3 4
5 0 1 2 4 5

출력
YES
YES
NO

예제 설명
첫번째 테스트 케이스에서, 가능한 답 중 하나는 $a = 0$, $b = 0$, $c = 0$, $d = 3$ 이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]