문제

2048 게임은 $4\times 4$ 격자 위에서 즐기는 게임이다. 원본 게임은 여기서 플레이할 수 있다. 게임의 규칙에 대한 자세한 설명은 2048 게임 1을 참고한다.

이 문제는 인터렉티브 문제다. 인터렉티브 문제란 문제에 대한 답을 단순히 출력하는 것이 아니라, 채점기와 상호작용하여 정답을 알아내는 문제다.

이 문제에서는 2048 게임 초기 상태에서, 움직임을 조작하여 512 타일을 만드는 것이 목표다. 조건을 잘 읽고 문제를 해결해 보자!

주요 게임 규칙은 다음과 같다

• 2048 게임 1에서의 게임 규칙 설명과 동일하나 아래 내용이 다르다.
• 게임이 처음 시작되면 총 두 개의 무작위 칸에 각각 90%의 확률로 2인 타일이, 10%의 확률로 4인 타일이 생성된다.
• 매 움직임 이후에 무작위 비어있는 칸 하나에 90%의 확률로 2인 타일이, 10%의 확률로 4인 타일이 생성된다.
• 사용자의 프로그램이 움직이려는 방향으로 움직여도 변화가 없다면 게임 오버가 되며 틀렸습니다를 받는다.
• 현재 격자 상태에서 네 방향 모두 움직여봐도 변화가 없다면 게임 오버가 되며 틀렸습니다를 받는다.
• 성공적으로 제한 시간 내에 512 타일을 만들었다면 맞았습니다를 받는다.

인터렉티브

입력의 편의를 위해 각 칸에는 위 그림과 같이 번호가 매겨져 있다.

게임은 다음과 같이 진행된다.

1. 게임이 시작되면 한 줄에 총 4개의 정수 a b c d가 공백으로 구분되어 입력으로 주어진다. ($1\le a, c\le 16; b, d \in \{2, 4\}$) 게임 초기에는 $a$번 칸에 $b$인 타일이 있고 $c$번 칸에 $d$인 타일이 있다는 의미다.

2. 이후, 여러분의 프로그램은 한 줄에 UP, DOWN, LEFT, RIGHT 중 하나를 출력해야 한다. 다만, 해당 방향으로 움직여도 변화가 없다면 틀렸습니다를 받으므로 주의하자!

3. 2번 이후 격자 내에 512 타일이 존재한다면 -1가 입력으로 주어지며 맞았습니다로 종료된다. 이때 여러분의 프로그램은 즉시 종료되어야 한다. 그렇지 않으면 예상하지 못한 결과를 얻을 수 있다.

4. 2번 이후 게임 오버 상태가 아니라면, 한 줄에 x y가 공백으로 구분되어 입력으로 주어진다. ($1\le x\le 16; y \in \{2, 4\}$) 현재 격자의 빈공간인 $x$번 격자에 $y$인 타일이 추가된다는 의미다. 다시 2번으로 돌아간다.

5. 2번 이후 게임 오버 상태라면, -1가 입력으로 주어지며 틀렸습니다로 종료된다. 이때 여러분의 프로그램은 즉시 종료되어야 한다. 그렇지 않으면 예상하지 못한 결과를 얻을 수 있다.

1 2 3 4

5 2

4 2

-1

 
LEFT

UP

UP

입출력이 어떤 방식으로 이루어지는지 이해를 돕기 위해, 의도적으로 줄 간격을 조절한 것이다. 실제 입출력과 다른 것에 유의하자.

1번 그림은 게임 초기 상태를 나타낸 것이다. 2번 그림은 1번 그림에서 LEFT를 수행했을 때의 게임 상태를 나타낸 것이다. 3번 그림은 2번 그림에서 UP을 수행했을 때의 게임 상태를 나타낸 것이다. 예제 출력 1에서는 3번 그림에서 추가로 UP을 했고 움직여도 변화가 없으므로 틀렸습니다를 받게 된다.

힌트

입출력 과정의 이해를 돕기 위해, 수동으로 입력을 넣어볼 수 있는 샘플 프로그램이 제공된다. sample.py

노트

타일 생성은 비적응적이며 완전히 무작위다. 틀렸습니다를 받았던 소스코드를 다시 제출했을 때 운이 좋으면 맞았습니다를 받을 수도 있다.