Magical BF 4

시간 제한1초메모리 제한1024 MB

요약

같은 격자를 행 순서와 열 순서로 읽어도 올바르게 동작하는 N×N 크기의 BF 코드를 작성하여 M0에 F_k를 구합니다.

난이도: 어려움10점 중 9점
유형: 구현, 시뮬레이션, 수학
정답자: 아직 제출이 없습니다

문제

존은 학교에서 많은 동아시아 언어가 왼쪽에서 오른쪽으로도, 위에서 아래로도 쓰일 수 있다는 것을 배웠다. 그는 한 텍스트를 두 방향으로 동시에 올바르게 읽을 수 있도록 쓸 수 있는지가 궁금했다. 프로그래밍 수업 시간에도 이 생각을 놓지 못한 존은 행 단위(위에서 아래, 왼쪽에서 오른쪽)로 읽을 때와 열 단위(왼쪽에서 오른쪽, 위에서 아래)로 읽을 때 모두 문제를 푸는 코드를 쓰고 싶어 한다. 이 실험에는 BF 언어를 골랐다.

BF 프로그램의 메모리는 왼쪽부터 $M_0$ , $M_1$ , ...으로 번호가 매겨진 무한한 배열 $M$ 이다. 각 셀에는 아무리 커질 수 있는 음이 아닌 정수가 들어 있다. 실행을 시작할 때 데이터 포인터는 가장 왼쪽 셀 $M_0$ 을 가리킨다.

실행은 첫 번째 명령에서 시작한다. 명령을 하나 실행할 때마다 프로그램은 순서상 다음 명령으로 넘어간다. 명령은 여섯 가지다.

명령	의미
`>`	데이터 포인터를 오른쪽으로 한 칸 옮긴다.
`<`	데이터 포인터가 가장 왼쪽 셀을 가리키지 않으면 왼쪽으로 한 칸 옮긴다. 그렇지 않으면 아무 일도 하지 않는다.
`+`	데이터 포인터가 가리키는 셀의 값을 1 증가시킨다.
`-`	데이터 포인터가 가리키는 셀의 값이 양수이면 1 감소시킨다. 그렇지 않으면 아무 일도 하지 않는다.
`[`	데이터 포인터가 가리키는 셀의 값이 0이면 짝이 되는 `]`로 앞으로 점프한다. 그렇지 않으면 아무 일도 하지 않는다.
`]`	데이터 포인터가 가리키는 셀의 값이 0이 아니면 짝이 되는 `[`로 뒤로 점프한다. 그렇지 않으면 아무 일도 하지 않는다.

아래 과제를 푸는 마법의 BF 프로그램을 존이 작성하도록 도와라. 해법은 $N \times N$ 격자에 채운 BF 코드이며, $1 \le N \le 1000$ 이다. 행 단위로 읽을 때와 열 단위로 읽을 때 코드가 같을 필요는 없지만, 두 경우 모두 과제를 정확히 풀어야 한다. 격자에는 >, <, +, -, [, ] 문자만 쓸 수 있고, 격자를 빈틈없이 채워야 한다. 허용되는 모든 입력에 대해 코드는 명령을 1000만 번보다 많이 실행해서는 안 된다.

셀 $M_0$ 에는 정수 $k$ ( $3 \le k \le 10$ )가 들어 있고, 셀 $M_1$ 과 $M_2$ 에는 정수 $F_1$ 과 $F_2$ ( $1 \le F_1 \le 3$ , $1 \le F_2 \le 3$ )가 들어 있다. $i > 2$ 인 수열의 원소 $F_i$ 는 $F_i = F_{i-1} + F_{i-2}$ 로 정의된다. $F_k$ 의 값을 구해 셀 $M_0$ 에 써라. 실행이 끝났을 때 $M_0$ 이외의 셀은 어떤 값이어도 된다.

예제1

예제 1
입력
```
3 1 1
```
예상 출력
```
2
```