SAVE the World (Large)

본 문제와 Small 문제는 점수 계산식과 제한이 다르다. "제한" 문단을 참조하라.

어느 날, 당신을 포함하여 총 $n+1$명의 용사가 이세계로 소환되었다. 당신은 용사들을 통솔할 수 있는 "지시" 능력을 부여받았다. 그러나 용사들이 이세계 곳곳에 흩어져 있어서, 마왕을 토벌하기 전에 모든 용사가 한 곳에 모일 필요가 있다. 따라서 당신은 용사들이 당신이 있는 곳으로 모일 수 있도록 그들 모두에게 "지시"를 내려야 한다.

이세계는 크기가 무한한 2차원 좌표평면으로 모델링할 수 있다. 당신은 현재 $(0,0)$에 있으며, 다른 모든 용사도 각각 서로 다른 정수 좌표 $(x,y)$에 있다. $(0,0)$에 있지 않은 모든 용사는 매 순간 자신의 좌표 $(x,y)$에서 $\max(|x'-x|,|y'-y|)=1$을 만족하는 $(x',y')$로 이동해야 한다. 즉, 어떤 용사가 $(x,y)$에 있다면 이 용사는 $(x-1,y)$, $(x-1,y-1)$, $(x,y-1)$, $(x+1,y-1)$, $(x+1,y)$, $(x+1,y+1)$, $(x,y+1)$, $(x-1,y+1)$ 중 한 곳으로 반드시 이동해야 한다.

용사에게 지시를 내리는 방법은 다음과 같다. 매 순간 $(0,0)$에 있지 않은 모든 용사는 인접한 8칸 중 한 곳으로 이동해야 한다. 키보드의 S 키를 중심으로 생각하면 쉽다. 용사가 $(x,y)$에 있을 때, 인접한 8칸에 대응하는 알파벳은 다음과 같다.

매 순간 알파벳을 하나씩 골라 문자열로 이어 붙이면 그 용사에 대한 "지시"가 된다. 예를 들어 $(1,1)$에 있는 용사에게 지시 $QXX$를 내리면, 용사는 $(0,2)$, $(0,1)$, $(0,0)$의 순서로 이동해 최종적으로 $(0,0)$에 도착한다. 또 $(-1,-1)$에 있는 용사에게 지시 $E$를 내리면, 용사는 한 번에 $(0,0)$에 도착한다. 전체 용사에 대한 지시는 각 용사와 그 용사에게 내리는 지시 사이의 일대일 대응으로 정의된다.

다만 용사에 대한 정보는 아직 비밀이고 용사를 소집하는 작전도 기밀이어서, 지시에는 다음과 같은 제약이 있다.

• 한 용사는 같은 좌표를 2번 이상 지날 수 없다. 즉, 어떤 순간에 용사가 좌표 $u$에서 좌표 $v$로 이동했다면, 그 용사는 좌표 $u$를 다시 방문할 수 없다.
• 어떤 순간에 2명 이상의 용사가 $(0,0)$을 제외한 어떤 좌표에도 동시에 있을 수 없다. 즉, 어떤 순간에 두 용사 A와 B가 좌표 $v$에 인접한 서로 다른 좌표에 있었다면, 두 용사가 동시에 $v$로 이동하는 것은 불가능하다. 다만 두 용사가 각각 $u$와 $v$를 차지하고 있을 때, 같은 순간에 자리를 바꾸어 각각 $v$와 $u$로 이동하는 것은 가능하다.
• 모든 용사는 동시에 현재 순간의 지시에 해당하는 다음 좌표로 이동해야 한다. 즉 현재가 순간 $i$라면, $(0,0)$에 있는 용사를 제외한 모든 용사는 자신의 지시에서 $i$번째 알파벳에 해당하는 좌표로 이동해야 한다.
• 어떤 용사가 $(0,0)$에 도착한 뒤에는 그 용사에게 더 이상 지시를 내리면 안 된다.
• 어떤 순간에 2명 이상의 용사가 동시에 $(0,0)$으로 이동할 수 없다. 즉 어떤 순간에 $(0,0)$에 도착하는 용사는 반드시 1명이거나 0명이어야 한다.

예를 들어 보자. 당신을 제외한 용사들이 현재 $(1,-1)$, $(1,0)$, $(1,1)$에 있다고 하자. 다음은 올바른 지시의 예이다.

예시 1. 올바른 지시의 예

반면 다음은 제약을 만족하지 않는 지시이다.

예시 2. 순간 1에 두 용사가 동시에 $(1,0)$을 차지하고 있다.

예시 3. 순간 1에 두 용사가 동시에 $(0,0)$으로 이동하고 있다.

예시 4. 한 용사가 $(1,-1)$을 2번 지나가고 있다.

다음 지시는 올바르다.

예시 5. 순간 1에 두 용사가 자리를 바꾸었지만, 이 지시는 여전히 올바르다.

과연 당신은 충분히 빠른 시간 안에 모든 용사를 $(0,0)$으로 모을 수 있을까?

첫 번째 줄에 당신을 제외한 용사의 수 $n$이 주어진다.

두 번째 줄부터 $n+1$번째 줄까지 용사의 좌표 $x_i$, $y_i$가 공백으로 구분되어 한 줄에 하나씩 주어진다.

$i$번째 줄에 $i$번째 용사에 대응하는 지시를 문자열로 출력한다.

• $1\le n\le 500$
• $-1000\le x_i,y_i\le 1000$
• 각 용사의 위치 $(x_i,y_i)$는 모두 서로 다르다.
• $(x_i,y_i)\neq(0,0)$

Large 문제의 각 테스트 케이스에 대해 지시의 점수는 다음과 같이 계산된다.

먼저 각 용사의 좌표 $(x_i,y_i)$에 대해 원점과의 $L^{\infty}$ 노름 값 $\max(|x_i|,|y_i|)$을 구한다. 이 값들을 정렬한 배열을 $P$라고 한다. 예를 들어 용사가 $(1,-1)$, $(1,0)$, $(1,2)$에 있다면 $P=[1,1,2]$이다.

다음으로 배열 $P$의 값을 이용해 길이 $n$의 배열 $C$를 다음과 같이 정의한다.

• $C_1=P_1$
• $i>1$일 때 $C_i=\max(C_{i-1}+1,P_i)$

모든 용사에 대한 지시 중 길이의 최댓값을 $L$이라 하고, 모든 테스트 케이스를 통틀어 제출한 코드의 최대 실행 시간을 $t$초라 하면, 각 테스트 케이스의 점수는 다음과 같다.

$10^6 \times \frac{C_n}{L} \times \min(1,{\epsilon}^{1-t}) \times V$

여기서 코드가 출력한 지시가 올바르고 모든 용사가 $(0,0)$에 모이는 데 성공하면 $V=1$이며, 그렇지 않으면 $V=0$이다. 점수는 실행 시간에 따라 달라진다. $\epsilon$의 값은 10이므로, 지시가 같더라도 $t=5.0$이면 $t=0.0$인 경우보다 약 10000배 작은 점수를 받는다.

Large 문제에는 250개의 테스트 케이스가 있으며, 총점수는 각 테스트 케이스 점수의 합이다.

Large 문제의 테스트 케이스는 다음 추가 조건을 따른다. 용사의 초기 위치 집합을 $S$라고 표기한다.

• 50개의 테스트 케이스는 다음 조건을 만족한다. $X=\{x \mid (x,y) \in S\}$, $Y=\{y \mid (x,y) \in S\}$, $O=\{x+y \mid (x,y) \in S\}$, $P=\{x-y \mid (x,y) \in S\}$라 하면 $\min(|X|,|Y|,|O|,|P|) \le 10$이다.
• 50개의 테스트 케이스는 다음 조건을 만족한다. $M=\{\max(|x|,|y|) \mid (x,y) \in S\}$라 하면 $|M| \le 10$이다.
• 50개의 테스트 케이스는 다음 조건을 만족한다. 두 좌표 $(x,y)$와 $(x',y')$에 대해 $\max(|x'-x|,|y'-y|)=1$이면 "인접함"이라고 정의한다. 이때 $(0,0)$과 인접한 용사는 단 한 명이며, 이 용사는 최대 1명의 다른 용사와 인접한다. 이 용사를 제외한 모든 용사는 최대 2명의 다른 용사와 인접한다.
• 50개의 테스트 케이스는 무작위로 생성되었다. 생성 방식은 다음과 같다. 이 방식은 가능한 용사 위치의 조합 ${4004000 \choose n}$가지를 균등한 확률로 뽑는다.
  • 범위 안에서 좌표 하나를 무작위로 뽑는다. 모든 좌표가 뽑힐 확률은 같다.
  • 이미 뽑은 좌표라면 위 단계로 돌아가 다시 뽑는다.
  • $n$개의 좌표가 뽑힐 때까지 두 단계를 반복한다.
• 나머지 테스트 케이스에는 입력 자체의 제한 외에 별도의 제한이 없다.

무작위 테스트 케이스를 생성하는 데 사용된 Generator의 소스 코드(gen_large.cpp)와 테스트 케이스를 시각화하는 도구(visualizer.html)가 제공된다. 테스트에 자유롭게 활용해도 좋다.

출력의 크기가 128MB를 초과하면 채점 결과는 '출력 초과'가 된다.