사이클 내부의 넓이

알고리즘

경로가 존재할 필요충분조건은 $N$이 짝수이고 다음 등식이 성립하는 것이다.

이 조건을 만족하지 않으면 No를 출력한다. 만족하면 Yes를 출력하고 다음 순서로 이동한다.

• U로 $N-1$번 이동하여 $(1,N)$에 도착한다.
• $x=2,3,\cdots,N$에 대해, 먼저 로 한 번 이동한다. 가 짝수이면 로 번, 홀수이면 로 번 이동한다.

가능한 경우에는 $N^2$개의 문자를 출력하므로 시간 복잡도는 $O(N^2)$이고, 불가능한 경우에는 $O(1)$이다. 전체 입력에 대한 시간 복잡도는 $O(T$이다.

서브태스크 1

$N\leq 4$에서는 방문한 점들을 기록하며 가능한 모든 경로를 완전탐색할 수 있다. 모든 점을 방문한 뒤 한 번 더 이동하여 시작점으로 돌아갈 수 있으면, 신발끈 공식으로 그 경로의 넓이를 계산한다. 구한 경로들을 넓이별로 저장하면 주어진 $K$에 맞는 경로를 찾을 수 있다.

첫 이동 이후에는 직전에 방문한 점으로 돌아갈 수 없으므로, 경로를 확장하는 각 단계에서 고려할 방향은 최대 $3$개이다. 한 크기 $N$에 대한 탐색 시간은 $O(3^{N^2})$이다. 가능한 크기가 뿐이므로 각 크기에 대해 한 번씩 탐색한 결과를 재사용한다.