28271번 - Overgrown-Puzzled 서브태스크언어 제한함수 구현

문제

여느 때와 다름없는 날, 선우는 학교 등굣길에 이상한 토끼 니키를 만나게 되었다. 니키는 회중시계를 든 채 바쁘다는 말만 중얼거릴 뿐이었다.

니키의 모습에 홀린 선우는 니키를 따라가기 시작하였다. 니키가 막다른 길에서 토끼굴로 들어가자, 선우는 조금 고민하다가 토끼굴에 뛰어들었다.

어느덧 시간이 지나 선우가 깨어보니 자기가 환상적인 장난감 나라 안 거대한 도넛 위로 불시착한 것을 깨달았다. 선우는 도넛의 겉모습을 확인해본 결과 등굣길에 들고 갔던 우유맛, 딸기맛, 초코맛 아이싱이 코팅된 도넛과 똑같은 모양인 것을 확인했다. 거대 도넛은 총 $n$개의 칸이 원형으로 붙어있으며 각 칸에는 0ドル$ 이상 $n-1$ 이하의 정수 번호가 붙어있다. 도넛의 0ドル$번 칸에서 시계 방향으로 $n$번 이동하면 1ドル,ドル 2ドル,ドル ..., $n-1,ドル 0ドル$번 칸이 순서대로 등장한다.

니키는 거대 도넛 탐사의 규칙을 아래와 같이 이야기하며 선우를 재촉하였다.

• 선우는 맨 처음 거대 도넛 위 임의의 위치로 불시착한다. 니키는 처음에 선우와 같은 칸에 있다.
• 선우는 시계 방향 또는 반시계 방향으로 한 칸 움직일 수 있다. 선우는 최대 $M$번 움직일 수 있다.
• 선우가 움직인 직후 니키가 움직인다. 니키는 선우가 움직이기 전에 밟은 칸과 현재 자신이 밟은 칸의 아이싱 종류를 비교하여 서로 다른 색일 때에만 선우가 움직인 방향과 동일하게 한 칸 움직인다. 만약 아이싱 종류가 같다면 니키는 움직이지 않는다.
• 선우와 니키가 움직이고 나서 선우는 니키가 자신과 같은 칸에 있는지 확인할 수 있다. 선우와 니키 사이의 거리 등 추가적인 정보는 알 수 없다.
• 선우는 언제든지 자신이 최초에 불시착한 칸의 번호를 이야기할 수 있다. 선우가 정답을 맞혔다면 니키가 새로운 세계로 선우를 데려갈 것이다.

선우는 이리저리 움직여 가며 자신의 위치를 파악해보려 했지만, 제대로 준비가 되지 않은 상태로 토끼굴에 뛰어드는 바람에 어찌할 방도가 없어서 결국 퍼즐 해결에 실패하였다.

선우는 니키의 토끼굴 너머 새로운 세계가 마음에 들었는지 도넛을 새로 만들어서 다시 토끼굴에 뛰어들기로 결심했다. 니키는 선우가 가져온 도넛의 크기에 따라 이동 횟수 제한을 다르게 이야기할 것이기 때문에 선우는 칸의 개수가 정확히 $N$개인 도넛을 만들어야 한다. 선우를 도와 니키의 첫 번째 퍼즐을 해결하는 프로그램을 작성하여라.

함수 목록 및 정의

여러분은 아래 함수를 구현해야 한다.

int[] decorate_donut(int N, int M)

• $N$: 선우가 들고 있는 도넛의 칸 개수
• $M$: 선우가 움직일 수 있는 최대 횟수
• 이 함수는 크기가 $N$인 배열 $D$를 반환해야 한다. $D[i]$는 도넛의 $i$번 칸에 들어갈 아이싱의 종류(우유맛은 0, 딸기맛은 1, 초코맛은 2)이다.

int explore_donut()

• 이 함수는 decorate_donut 함수의 반환값으로 만든 도넛에 선우가 불시착하여 선우가 이리저리 돌아다니면서 자신의 위치를 파악하는 함수이다. 이 함수는 선우가 불시착한 최초 위치 $pos$ (0ドル \leq pos < N$)를 반환해야 한다.

여러분은 explore_donut 함수 안에서 아래 함수를 호출할 수 있다.

int move(int dir)

• $dir$: 선우가 움직이는 방향. $dir$ 은 1ドル$ 또는 $-1$이어야 한다.
• $dir$이 1ドル$이면 선우가 시계 방향으로 한 칸 움직이며, $dir$이 $-1$이면 선우가 반시계 방향으로 한 칸 움직인다. 니키는 선우와 자신의 서 있는 칸에 따라 적절하게 움직인다. 함수의 반환값은 선우와 니키가 움직인 이후 같은 칸에 있으면 1ドル$을, 아니면 0ドル$이다.
• 각 explore_donut 함수 당 move 함수를 $M$번보다 많이 호출하거나 잘못된 인자로 호출한 경우 프로그램이 즉시 종료되며 틀렸습니다를 받게 된다.

그레이더는 decorate_donut 함수를 먼저 호출한 다음 explore_donut 함수를 1ドル$번 이상 $N$번 이하로 호출한다. 모든 explore_donut 함수 호출에 대하여 정답을 반환해야 맞았습니다를 받는다.

제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.

입력

출력

제한

서브태스크

힌트

예제 1

도넛의 칸 수 $N = 6$이고 여러분이 decorate_donut 함수의 반환값으로 [0, 1, 2, 1, 1, 0]를 반환한 경우를 생각해보자.

여러분이 move(1)을 1ドル$번, move(-1)을 3ドル$번 호출해서 나온 함수의 반환값이 순서대로 0, 0, 0, 1이라고 하자.

1. 선우의 첫 위치가 0ドル$이라면, 함수의 반환값은 0, 0, 1, 0이어야 한다.
2. 선우의 첫 위치가 1ドル$이라면, 함수의 반환값은 0, 0, 0, 1이어야 한다.
3. 선우의 첫 위치가 2ドル$이라면, 함수의 반환값은 0, 0, 0, 0이어야 한다.
4. 선우의 첫 위치가 3ドル$이라면, 함수의 반환값은 0, 1, 0, 0이어야 한다.
5. 선우의 첫 위치가 4ドル$이라면, 함수의 반환값은 0, 0, 1, 0이어야 한다.
6. 선우의 첫 위치가 5ドル$이라면, 함수의 반환값은 0, 1, 0, 0이어야 한다.

따라서 여러분은 explore_donut 함수의 반환값으로 1ドル$을 반환해야 한다.

샘플 그레이더

샘플 그레이더는 첫 번째 줄에 $N,ドル $M$과 explore_donut의 호출 횟수 $T$을 입력받는다. 두 번째 줄부터 $T$개의 줄에는 매 explore_donut 때 선우가 불시착한 위치 $pos$에 해당하는 정수를 입력받는다.

샘플 그레이더는 여러분이 구현한 함수가 올바르게 동작했는지 여부를 출력한다.

실제 채점에서 사용하는 그레이더는 샘플 그레이더와 다를 수 있음에 유의하라. 그레이더는 비적응적(non-adaptive)으로 매 explore_donut 함수 호출에 대해 미리 선우의 불시착 위치를 정한 다음 여러분의 함수 호출 상황에 따라 정답을 바꾸지 않는다.

첨부

• overgrown_puzzled.zip