무리무리 수열

방정식 $ax^2+bx+c=0$이 실근을 가지려면 판별식 $b^2-4ac$가 음수가 아니어야 한다. 특히 $ac\leq0$이라면 이 조건은 항상 만족한다.

따라서 수열에서 두 칸 떨어진 두 수가 서로 반대 부호를 갖도록 만들자. 먼저 부호를 다음과 같이 배치한다.

$$0,+,-,-,+,+,-,-,+,+,\ldots$$

$0$ 뒤에서는 길이 $4$의 패턴 $+,-,-,+$가 반복된다. 이 패턴에서는 두 칸 떨어진 두 항의 부호가 항상 반대이다. 첫 번째 항이 포함된 경우에는 두 항의 곱이 $0$이다.

$1$번째 이후의 $2N$개 위치에는 양수 위치와 음수 위치가 각각 정확히 $N$개씩 존재한다. 양수 위치에는 $1,2,\ldots,N$을 차례대로, 음수 위치에는 $-1,-2,\ldots,-N$을 차례대로 넣는다. 그러면 부터 까지의 모든 정수를 정확히 한 번 사용한다.

임의의 연속한 세 항을 $a,b,c$라고 하자. 위 구성에 의해 $ac\leq0$이므로

$$b^2-4ac\geq b^2\geq0$$

이다. 따라서 모든 방정식이 실근을 하나 이상 갖는다.

시간 복잡도는 출력 크기와 같은 $O(N)$이고, 추가 공간 복잡도는 $O(1)$이다.

Solution written by GPT6