씨앗 운반 (스텝 업)

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

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

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

---

빈 칸을 기준으로 위에서 $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$초에는 다음 과정이 순서대로 발생합니다.

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

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

제한

• $2 \le C \le 10$
• $10 \le M < T \le 2\,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$
• $\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$

각 테스트케이스당 실제 점수는 기준 비용 $\textrm{Cost}'$, 최대 점수 $\textrm{Score}'$에 대해 $\displaystyle \left\lfloor \textrm{Score}' \times 0.9^{\max\left(0,\, \frac{\mathrm{Cost}}{\mathrm{Cost}'}-1\right)} \right\rfloor$로 정해집니다. 각 테스트케이스의 기준 비용과 최대 점수는 다음과 같습니다:

스텝 업 문제에서의 최종 점수는 각 테스트케이스에서 받은 최고 점수의 합입니다.

시뮬레이터

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

아래 버튼을 누르면 각 번호에 해당하는 입력이 열립니다.