아, 예스터데이 원스 모어

2018년에는 난징항공항천대학(NUAA)이 주최하여 몇 년 만에 국제 대학생 프로그래밍 콘테스트(ICPC) 지역 대회가 다시 난징에서 열렸다. 이 대회에는 $400$개가 넘는 팀이 참가했고 칭화대학교의 Power of Two 팀이 우승했다.

2년이 지나 2018년과 2019년의 큰 성공을 거둔 후, NUAA는 2020년에도 ICPC 난징 지역 대회를 계속 개최한다. 이번에는 팬데믹으로 인해 난징에서 모일 수 없지만, 이 대회를 위해 수고한 모든 스태프와 자원봉사자들에게 감사해야 한다. 이 대회에 큰 기여를 해주신 모든 분들께 감사드린다!

2018 ICPC 아시아 난징 지역 대회

2018년 대회에서 K번 문제인 Kangaroo Puzzle은 참가자들이 게임을 위한 연산 순서를 구성하도록 요구했다. 먼저 그 문제의 내용을 떠올려 보자:

퍼즐은 $n$행 $m$열($1 \le n, m \le 20$)의 격자이며, 퍼즐 안에는 몇 마리(적어도 $2$마리)의 캥거루가 서 있다. 플레이어의 목표는 캥거루들을 한 곳에 모으는 것이다. 일부 칸에는 벽이 있어 캥거루는 벽이 있는 칸에 들어갈 수 없다. 다른 칸들은 비어 있다. 캥거루는 빈 칸에서 상하좌우 네 방향으로 인접한 빈 칸으로 이동할 수 있다. 캥거루는 어떤 빈 칸에서든 인접한 빈 칸을 통해 다른 어떤 빈 칸으로도 이동할 수 있음이 보장된다. 또한 퍼즐에는 사이클이 없음이 보장된다. 즉, 한 캥거루가 빈 칸에서 출발하여 여러 개의 서로 다른 빈 칸을 거쳐 원래 칸으로 돌아오는 것은 불가능하다.

처음에는 모든 빈 칸에 정확히 한 마리의 캥거루가 있고, 플레이어는 키보드의 U, D, L, R 버튼을 눌러 캥거루를 조종할 수 있다. 캥거루들은 누른 버튼에 따라 동시에 움직인다. 예를 들어 R 버튼을 누르면, 캥거루는 오른쪽 칸이 존재하고 비어 있으면 한 칸 오른쪽으로 이동하고, 존재하지 않거나 비어 있지 않으면 가만히 있는다.

이 문제에서 참가자는 U, D, L, R만으로 이루어진 길이 $5 \times 10^4$ 이하의 연산 순서를 구성해야 한다. 이 단계들을 순서대로 수행한 후에도 서로 다른 칸에 두 마리의 캥거루가 남아 있으면 참가자는 "Wrong Answer" 판정을 받는다.

우리의 친구 Kotori도 이 대회에 참가하여 무작위 알고리즘 코드를 제출했다. 놀랍게도 이 단순한 해법이 정답으로 판정되었다. 이제 그 해법을 소개한다:

#include <bits/stdc++.h>
char s[5] = 'UDLR';
using namespace std;
int main()
{
  srand(time(NULL));
  for (int i = 1; i <= 50000; i++) putchar(s[rand() % 4]);
  return 0;
}

C와 C++에 익숙하지 않은 참가자를 위해 설명하자면, 위 코드는 'U', 'D', 'L', 'R' 문자로만 이루어진 길이 $5 \times 10^4$의 무작위 문자열을 출력하며, 각 문자는 문자열의 각 위치에 같은 확률로 나타난다.

Kotori는 이 문제가 그렇게 간단하지 않을 수 있다고 의심한다. 그래서 지금 이 2020 ICPC 난징 지역 대회에서 당신은 그녀의 해법을 해킹할 입력 데이터를 구성해야 한다. 무작위성 때문에 당신의 입력 데이터는 $25\%$ 이상의 해킹 성공률만 만족하면 된다. 공식적으로 말하자면, Kotori의 코드에 따라 무작위로 생성된 $500$개의 문자열을 준비했고, 이를 당신의 답에 대한 조종 순서로 사용할 것이다. 당신의 답이 정답으로 인정되려면, 당신의 답을 칸 지도로 사용하고 전체 조종 순서를 실행한 후에도 서로 다른 칸에 캥거루가 남아 있는 경우가 적어도 $125$번 있어야 한다.

당신의 입력 데이터는 완전히 합법적이어야 한다. 즉,

• 당신의 답에 있는 지도는 $20 \times 20$보다 크면 안 된다.
• 당신의 답에는 적어도 두 개의 빈 칸이 있어야 한다.
• 당신의 답에 있는 모든 빈 칸은 어떤 빈 칸에서 출발해도 도달할 수 있어야 한다.
• 빈 칸으로 이루어진 사이클은 허용되지 않는다.

이 문제에는 입력이 없다. 스스로 해결해야 한다!

먼저 한 줄에 두 정수 $n$과 $m$($1 \le n, m \le 20$)을 공백으로 구분하여 출력한다. 이는 당신의 답에 있는 지도의 행 수와 열 수를 나타낸다.

그런 다음 $n$개의 줄을 출력한다. $i$번째 줄에는 길이 $m$의 이진 문자열 $s_{i,1}s_{i,2}\cdots s_{i,m}$($s_{i,j} \in \{\text{'0'}, \text{'1'}\}$)이 있다. $s_{i,j} = \text{'1'}$이면 $i$번째 행 $j$번째 열의 칸은 비어 있고, 그렇지 않으면 해당 칸에는 벽이 있어 들어갈 수 없다.

다시 말하지만, 당신의 답은 $25\%$ 이상의 해킹 성공률만 달성하면 된다. 그렇게 어렵지 않지 않은가?

우리가 제공하는 예시 출력은 (당연히) 틀렸다. 이는 출력 형식을 보여주기 위한 목적으로만 제공된다. 이것은 $4$개의 벽이 있는 $3 \times 4$ 지도이므로, 처음에 빈 칸에는 $8$마리의 캥거루가 있을 것이다.