시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 417 | 175 | 148 | 42.165% |
지학이는 3차 다항식(cubic polynomial)을 좋아하는 잘 알려진 cubelover 이다.
어느 화창한 봄날, 지학이는 아파트 놀이터에서 승현이가 길이 n의 정수 수열 x1, x2, ..., xn 을 가지고 노는 것을 보았다. 지학이는 그 아파트의 짱이었고, 승현이보다 45일이나 먼저 태어난 형이었다. 지학이는 승현이를 보자 마자 갖고 놀던 수열을 빼앗아 갔다.
승현이는 그 자리에서 엉엉 울기 시작했고, 마음이 약해진 지학이는 승현이가 1 ≤ i ≤ n인 모든 정수 i에 대해 xi = ai3+bi2+ci+d를 만족하는 실수 a, b, c, d 를 찾으면 수열을 돌려주겠다고 약속했다. (사실 3차 다항식이라 a ≠ 0이어야 하긴 하는데, 지학이는 그 정도로 엄밀하게 굴고 싶진 않은 모양이다.)
간만에 학교를 나와 외출을 즐기고 있는 당신은, 울고 있는 승현이와 눈을 마주쳤다. 승현이는 여러분에게 곧장 달려와서, 빨리 그러한 실수 a, b, c, d 를 찾아달라고 졸랐다. 당신은 과연 승현이의 눈물을 닦아 줄 수 있는가?
이 문제는 한 입력에 여러 개의 테스트 케이스가 주어진다. 첫 번째 줄에 그러한 테스트 케이스의 개수 T (1 ≤ T ≤ 1000) 가 주어진다.
이후 T개의 줄이 주어진다. 첫 번째로 수열의 길이인 정수 n (1 ≤ n ≤ 500) 이 주어진다. 이후 n 개의 정수가 주어진다. 이 중 i번째 정수는 xi (0 ≤ xi ≤ 50, 000, 000) 를 뜻한다.
T개의 줄에 걸쳐, 만약에 승현이가 원하는 실수 a, b, c, d가 존재한다면 YES, 존재하지 않는다면 NO를 출력한다.
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 이다.