(여기에 이름 입력) Sequence

먼저 $N\leq3$인 경우를 확인하자.

• $N=1$이면 정의에 따라 $A=0<S=1$이다.
• $N=2$이면 유일한 인접 쌍의 OR 값은 $1\mathbin{\mathrm{OR}}2=3=S$이다.
• $N=3$이면 서로 다른 두 수의 OR 값이 항상 $3$이므로 $A=6=S$이다.

따라서 이 세 경우에는 조건을 만족하는 순열이 없다.

이제 $N\geq4$라고 하자. 순열

$$P=(1,2,3,\ldots,N)$$

을 출력하면 된다.

모든 $i$에 대해 $i\mathbin{\mathrm{OR}}(i+1)\geq i+1$이다. 따라서

$$A\geq\sum_{i=1}^{N-1}(i+1)=S-1$$

이다. 여기서 첫 번째 항은 $1\mathbin{\mathrm{OR}}2=3$이므로 하한보다 $1$ 크고, 네 번째 수까지 존재하므로 $3\mathbin{\mathrm{OR}}4=7$은 하한에 사용한 $$보다 크다. 따라서

$$A\geq(S-1)+1+3>S$$

이 성립한다.

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

Solution written by GPT6

+ $N \ge 4$인 경우 어떤 순열을 출력하든 항상 문제의 조건을 만족한다.