씨앗 운반 (챌린지)

$(R+2)$ 행 $C$ 열 격자 모양의 들판이 있습니다. 가장 위쪽 행에는 씨앗이 떨어지는 꽃이, 가장 아래쪽 행에는 씨앗을 저장하는 굴이 한 칸에 하나씩 총 $C$ 개 있으며, 가운데 $R$ 개의 행은 모두 빈 칸입니다. 이 문제에서 당신의 임무는

빈 칸으로 이루어진 행의 개수 $R$ 을 설정하고,
빈 칸에 다람쥐 혹은 햄스터를 적절히 배치하고, 씨앗을 옮길 방법을 정하는 것

입니다. 당신은 각 꽃에서 떨어지는 씨앗을 최대한 요구치에 가깝게 각 굴로 옮겨야 합니다.

씨앗 운반 – 스텝업 1번
이미지

빈 칸을 기준으로 위에서 $r$ 번째 행, 왼쪽에서 $c$ 번째 열에 해당하는 칸을 $(r, c)$ 라고 합시다. 또한, 가장 위쪽 행의 꽃은 각각 $(0, 1), (0, 2), \cdots, (0, C)$ , 가장 아래쪽 행의 굴은 각각 $(R+1, 1), (R+1, 2), \cdots, (R+1, C)$ 라고 합시다.

꽃 $(0, i)$ 에서는 씨앗이 $A_i$ 개 열립니다.
굴 $(R+1, i)$ 까지 씨앗을 $B_i$ 개 옮기려고 합니다.
꽃에 열리는 씨앗의 총 개수와, 굴까지 옮겨야할 씨앗의 총 개수는 같습니다. 즉, $A_1 + A_2 + \cdots + A_C = B_1 + B_2 + \cdots + B_C$ 입니다.
가장 많은 씨앗이 열리는 꽃에서는 $M$ 개의 씨앗이 열립니다. 또한, 각 굴에서 요구하는 씨앗의 최대 개수는 $M$ 이하입니다. 즉, $\max(B_1, B_2, \cdots, B_C) \le \max(A_1, A_2, \cdots, A_C) = M$ 입니다.

격자의 빈 칸에는 다람쥐 혹은 햄스터를 배치할 수 있습니다. 각 다람쥐 혹은 햄스터는 자신의 칸의 씨앗을 정해진 규칙에 따라 다른 칸으로 옮깁니다.

다람쥐: 상하좌우로 인접한 칸으로 씨앗을 보낼 수 있습니다. ↑, ↓, ←, → 중 원하는 방향을 원하는 순서대로 고르면, 해당 칸으로 씨앗을 배분합니다.
햄스터: 같은 행이나 같은 열에 있는 인접하지 않은 칸을 골라서 멀리 씨앗을 보낼 수 있습니다.

배치가 끝나면, $T$ 초에 걸쳐 씨앗 운반이 시작됩니다. 각 시각 $t = 1, 2, \cdots, T$ 초에는 다음 과정이 순서대로 발생합니다.

씨앗 수확: 각 꽃 $(0, i)$ 는 $t = M-A_i+1, M-A_i+2, \cdots, M$ 인 동안 씨앗을 $1$ 개씩 $(1, i)$ 로 떨어뜨립니다.
씨앗 보내기: 모든 다람쥐와 햄스터가 동시에 자신의 칸에 있는 씨앗을 다른 칸으로 보냅니다.
- 다람쥐: 각 다람쥐는 지난번에 마지막으로 씨앗을 보냈던 방향의 다음 순서부터 시작하여, 고른 방향 순서대로 돌아가며 씨앗을 한 개씩 보냅니다. 같은 방향으로는 최대 한 개씩만 보냅니다.
- 햄스터: 자신의 칸에 씨앗이 있다면 정해진 다른 칸으로 씨앗을 $\textbf{1}$ 개 보냅니다.
- 이 과정에서 칸에 있는 모든 씨앗을 다른 칸으로 보내지 못한 경우, 칸이 과부하됩니다.
  - 빈 칸 혹은 굴에 남아있는 씨앗을 옮길 다람쥐 혹은 햄스터가 없는 경우도 마찬가지로 과부하됩니다.
- 예시: 다람쥐에게 4개의 칸을 골라 [↑, ↓, ←, →] 순서로 보내도록 지정한 경우,
  - 시각 $\textbf{T}$ : 칸에 씨앗이 $\textbf{2}$ 개 있다면, ↑, ↓로 씨앗을 한 개 보냅니다.
  - 시각 $\textbf{T+1}$ : 칸에 씨앗이 $\textbf{3}$ 개 있다면, ↓ 다음 순서인 ←부터 시작해서 ←, →, ↑으로 씨앗을 한 개 보냅니다.
  - 시각 $\textbf{T+2}$ : 칸에 씨앗이 $\textbf{6}$ 개 있다면, ↑ 다음 순서인 ↓부터 시작해서 ↓, ←, →, ↑으로 씨앗을 한 개 보냅니다. 남은 씨앗 $\textbf{2}$ 개는 가지고 있습니다. 해당 칸은 과부하된 칸이 됩니다.
씨앗 받기: 과부하된 칸이 바로 직전의 씨앗 보내기 단계에서 받은 모든 씨앗을 원래 칸으로 되돌려놓습니다.
씨앗 저장: $(R + 1, i)$ 에 씨앗이 떨어져 있다면, 씨앗 $1$ 개가 굴 안으로 굴러떨어집니다. 이 씨앗은 더 이상 운반될 일이 없습니다.

입력 형식

첫 줄에 $C, T, M$ 이 공백으로 구분되어 주어집니다.

다음 줄에 $A_1, A_2, \cdots, A_C$ 가 공백으로 구분되어 주어집니다.

다음 줄에 $B_1, B_2, \cdots, B_C$ 가 공백으로 구분되어 주어집니다.

출력 형식

첫 줄에 사용하기로 결정한 격자판 행의 개수 $R$ 을 출력합니다. $R$ 은 $C$ 이상 $C+20$ 이하의 수여야 합니다.

다음 줄부터 $R$ 개의 줄 각각에 $C$ 개의 문자열을 공백으로 구분하여 출력합니다. $r$ 번째 줄의 $c$ 번째 문자열은 $(r, c)$ 에 있는 다람쥐가 씨앗을 전달하는 방법을 의미합니다. 위쪽을 U, 아래쪽을 D, 오른쪽을 R, 왼쪽을 L이라는 문자로 표현합니다. 꽃으로는 씨앗을 보낼 수 없습니다.

다람쥐: 고른 방향을 순서대로 공백 없이 붙여서 표현합니다. 만약 고른 방향이 없다면 X로 표시합니다.
- [위, 아래, 오른쪽] 은 UDR로 표현합니다.
햄스터: 고른 격자칸까지의 거리와 방향을 차례대로 공백 없이 붙여서 표현합니다.
- $12$ 칸 아래의 격자칸으로 씨앗을 던지고 싶다면 12D 로 표현합니다.

제한

$5 \le C \le 10$
$T = 2\,000\,000$
$100\,000 \le M \le 1\,000\,000$
$0 \le A_i \le M$ $(1 \le i \le C)$
$0 \le B_i \le M$ $(1 \le i \le C)$
$A_1 + A_2 + \cdots + A_C = B_1 + B_2 + \cdots + B_C = 1\,000\,000$
$\max(A_1, A_2, \cdots, A_C) = M$

채점

챌린지 문제는 전체 문제의 점수의 50% 비중을 차지합니다.

올바르지 않은 출력을 한 경우, 즉, 출력 형식을 맞추지 않았거나, 존재하지 않은 칸에 씨앗을 던지려 한 경우 $0$ 점입니다.

아닌 경우, $T$ 초가 끝난 이후 $(R+1, i)$ 에 있는 씨앗 굴에 있는 씨앗의 개수를 $B'_i$ 라고 할 때

오차: 운반해야 하는 씨앗 개수와, 실제로 운반된 씨앗 개수의 차이 합 $E = \sum_{i=1}^C \lvert B'_i - B_i \rvert$
손실: 굴로 운반되지 못한 씨앗의 개수 $L = \sum_{i=1}^C B_i - \sum_{i=1}^C B'_i$
지연: $L > 0$ 이라면 $D = T$ , 아닐 경우 마지막 씨앗이 굴로 들어간 시간을 $T_{\textrm{last}}$ 라고 할 때, $D = T_\textrm{last} - M$

이때 비용은 다음과 같은 방법으로 정해집니다.

$\textrm{Cost} = 2^{R-C}+\max(E, D) + T\times L$
비용이 낮을수록 더 좋은 결과입니다.

이때의 각 테스트케이스의 점수는 다음과 같은 방법으로 정해집니다.

전체 참가자의 수: $n_\textrm{tot}$
자신보다 비용이 낮은 참가자의 수: $n_\textrm{lose}$
자신과 비용이 같은 다른 참가자의 수: $n_\textrm{draw}$
$\textrm{Score} = \left\lfloor 10^6 \left(1 - 0.5\sqrt{\dfrac{n_\textrm{lose} + 0.5 n_\textrm{draw}}{n_\textrm{tot}}}\right) \right\rfloor$

챌린지 문제의 최종 점수는 최종 평가에 사용된 각 테스트 케이스 점수의 평균이 됩니다. 비슷하게, 중간 평가의 점수는 중간 평가에 사용된 각 테스트 케이스 점수의 평균이 되며, 이 점수는 참고용으로 최종 점수에 반영되지 않습니다. 평가에는 예제 코드보다 낮은 비용을 받은 제출만 채점됩니다.

문제의 점수는 각 테스트 케이스 별로 매겨지며, 최종 점수는 테스트 케이스별 점수의 평균으로 계산됩니다.

시뮬레이터

문제 풀이에 도움이 되는 시각화 도구를 제공합니다. 바로가기

예제 코드

대회에서 지원하는 각 언어로 작성된 예제 코드를 아래에서 확인할 수 있습니다.

데이터 제작 방법

$X$ 가 $a$ 이상 $b$ 이하에서 선택되었다는 것을 $X \sim \mathcal{U}\{a; b\}$ 으로 표현합니다.
특정 범위에서 정수를 고를 때, 해당 범위에서 모든 수가 선택될 확률은 동일하며, 모든 시행은 독립입니다.

데이터는 다음과 같은 방법으로 생성됩니다.

$T = 2\,000\,000$
$C\sim \mathcal{U}\{5; 10\}$
다음과 같은 방법으로 수열 $N_1, N_2, \cdots, N_C$ $N_{1}, N_{2}, \dots, N_{C}$ 를 두 개 생성합니다.
- $i = 1, \cdots, C-1$ 에 대해 $X'_i \sim \mathcal{U}\{1; 1\,000\,000+C-1\}$ .
- $X'_1, X'_2, \cdots, X'_{C-1}$ 에 중복된 원소가 있으면 수열을 다시 뽑습니다.
- $X'_1, X'_2, \cdots, X'_{C-1}$ 를 오름차순으로 정렬한 수열을 $X_1, X_2, \cdots, X_{C-1}$ 로 놓습니다.
- $X_0 = 0, X_C = 1\,000\,000 + C$ 라고 놓은 이후, $N_i = X_i - X_{i-1} - 1$ 로 놓습니다. $(1 \le i \le C)$
생성한 두 수열 중 원소의 최댓값이 큰 쪽을 $A$ , 작은 쪽을 $B$ 로 정합니다. 최댓값이 같은 경우 먼저 생성한 수열이 $A$ 입니다.

중간 평가 데이터 제작 방법

각 중간 평가 별로 $30$ 개의 데이터가 사용됩니다.

각 데이터의 $C$ 를 선택하는 부분이 다음과 같이 대체됩니다.
데이터를 모두 생성한 이후 계산한 $M$ 의 값이 해당 범위 밖이라면 데이터 생성을 처음부터 다시 시작합니다.

번호	$C$	$M$ 범위 ( $MN \le M \le MX$ )
1	$5$	$200\,000\le M \le 421\,816$
2	$5$	$421\,817\le M \le 479\,291$
3	$5$	$479\,292\le M \le 539\,215$
4	$5$	$539\,216\le M \le 618\,806$
5	$5$	$618\,807\le M \le 1\,000\,000$
6	$6$	$166\,667\le M \le 376\,195$
7	$6$	$376\,196\le M \le 427\,656$
8	$6$	$427\,657\le M \le 481\,244$
9	$6$	$481\,245\le M \le 554\,261$
10	$6$	$554\,262\le M \le 1\,000\,000$
11	$7$	$142\,858\le M \le 340\,734$
12	$7$	$340\,735\le M \le 387\,307$
13	$7$	$387\,308\le M \le 435\,920$
14	$7$	$435\,921\le M \le 502\,939$
15	$7$	$502\,940\le M \le 1\,000\,000$
16	$8$	$125\,000\le M \le 312\,245$
17	$8$	$312\,246\le M \le 354\,780$
18	$8$	$354\,781\le M \le 399\,301$
19	$8$	$399\,302\le M \le 461\,116$
20	$8$	$461\,117\le M \le 1\,000\,000$
21	$9$	$111\,112\le M \le 288\,765$
22	$9$	$288\,766\le M \le 327\,921$
23	$9$	$327\,922\le M \le 368\,995$
24	$9$	$368\,996\le M \le 426\,322$
25	$9$	$426\,323\le M \le 1\,000\,000$
26	$10$	$100\,000\le M \le 269\,020$
27	$10$	$269\,021\le M \le 305\,310$
28	$10$	$305\,311\le M \le 343\,441$
29	$10$	$343\,442\le M \le 396\,873$
30	$10$	$396\,874\le M \le 1\,000\,000$