정령과 눈 감고 숨바꼭질 게임

Semia와 9명의 친구들은 놀이터에서 눈을 감고 진행하는 숨바꼭질 게임을 하고 있다. 이 게임은 술래가 눈을 감고 놀이터 곳곳에 숨어있는 나머지 9명을 찾아내는 게임이다. 놀이터는 $200 \times 200$ 크기의 격자이다. 격자의 $i$행 $j$열을 $(i, j)$로 표기한다. $(0 \le i, j \le 199)$

게임이 시작하기 전, 술래가 아닌 나머지 9명은 격자에서 한 칸을 골라 그 곳에 숨는다. 한 칸에 여러 사람이 숨을 수도 있다. 이후 술래는 코끼리 코를 돌아서 중앙의 $100 \times 100$ 크기 격자의 무작위 위치에서 다른 친구들을 찾기 시작한다. 이 때 코끼리 코를 매우 격렬하게 돌기 때문에, 술래는 자신이 시작하는 위치가 정확히 어디인지조차 알지 못한다. 하지만 술래의 시작 위치를 $(i\_{0}, j\_{0})$라고 하면 $50 \le i\_{0}, j\_{0} \le 149$임은 보장할 수 있다.

나머지 9명의 위치를 $(i\_{k}, j\_{k})$ $(1 \le k \le 9)$ 라고 하자. 술래에게 너무 빨리 들키는 것을 방지하기 위해 모든 $1 \le k \le 9$에 대해 $\lvert i\_{k} - i\_{0} \rvert > 1, \lvert j\_{k} - j\_{0} \rvert > 1$ 를 만족할 때만 정상적으로 게임을 시작한다. 그렇지 않으면 게임을 다시 시작할 것이므로 무시해도 좋다.

이번 게임에서는 Semia가 술래가 되었다. 게임을 이기고 싶은 Semia는 친구들을 찾기 전 남들 몰래 정령을 불러내서 정령의 도움을 받으려고 한다. 정령은 나머지 9명이 숨은 위치를 보고 놀이터의 모든 격자 칸에 양의 정수를 적어 표시해 놓으려고 한다. 안타깝게도 정령은 1부터 24까지의 수밖에 모르기 때문에 1 이상 24 이하의 정수만 표시해 놓을 수 있다. 

Semia는 정령이 표시해둔 수를 이용해 나머지 9명의 위치를 파악하려고 한다. Semia는 마나를 사용해 다음의 두 가지 능력을 사용할 수 있다. 안타깝게도 두 능력은 마나를 많이 소모하는 행동이라 각각 사용할 수 있는 횟수에 제한이 있다.

• Find x. 값 $x$가 표시된 격자들 중 유클리드 거리로 가장 가까운 격자가 어디 있는지, 현재 위치를 기준한 상대적인 좌표로 알 수 있다. 조건을 만족하는 격자의 위치가 $(u, v)$라면, Semia는 $(u - i\_{0}, v - j\_{0})$를 알 수 있는 것이다. 이 능력은 최대 한 번 사용할 수 있으며, 가장 가까운 격자가 여러 개인 경우 그 중 아무 한 점의 좌표만 알아낼 수 있다.
• Get x y. Semia 기준 상대 좌표가 $(x, y)$인 위치, 다시 말해 $(i\_{0} + x, j\_{0} + y)$에 정령이 표시한 값을 알 수 있다. 이 때 $|x| \leq 1, |y| \leq 1$이어야 한다. 이 능력은 최대 네 번까지 사용할 수 있다.

Semia는 나머지 9명이 각각 자신을 원점으로 하는 사분면 중 어디에 속해있는지 구하려고 한다. 사분면은 아래와 같이 번호를 붙인다.

• $i - i\_{0} > 0, j - j\_{0} > 0$인 경우 $(i, j)$는 1사분면에 속한다.
• $i - i\_{0} < 0, j - j\_{0} > 0$인 경우 $(i, j)$는 2사분면에 속한다.
• $i - i\_{0} < 0, j - j\_{0} < 0$인 경우 $(i, j)$는 3사분면에 속한다.
• $i - i\_{0} > 0, j - j\_{0} < 0$인 경우 $(i, j)$는 4사분면에 속한다.
• $i - i\_{0}, j - j\_{0}$ 중 하나 이상이 $0$인 경우는 이 문제에서 고려할 필요가 없다.

Semia와 정령을 도와 두 명의 전략을 구현해보자!

함수 목록 및 정의

Grader에서 기본으로 제공하는 함수는 다음과 같다. 여러분은 이 함수들을 적절히 호출하여 문제를 해결해야 한다.

pair<int, int> Find(int x)

• 값 $x$가 표시된 격자들 중 유클리드 거리로 가장 가까운 격자의 Semia 기준 상대 좌표를 반환하는 함수이다. 가장 가까운 격자가 여러 개 존재하면 그 중 무작위로 선택된 하나에 대한 값을 반환한다.
• 정령이 칸에 표시해 놓은 값들 중 $x$가 존재해야 한다. 이를 만족하지 않은 경우, "틀렸습니다"를 받는다.
• 이 함수를 1번보다 많이 호출할 경우 "틀렸습니다"를 받는다.

int Get(int x, int y)

• Semia 기준 상대 좌표가 $(x, y)$인 위치에 표시된 값을 반환하는 함수이다.
• $|x| \leq 1, |y| \leq 1$ 을 만족하지 않는 경우 "틀렸습니다"를 받는다.
• 이 함수를 4번보다 많이 호출할 경우 "틀렸습니다"를 받는다.

여러분은 다음 두 함수를 구현해야 한다. 

vector< vector<int> > play_spirit(vector< pair<int, int> > &hider_positions)

• 인자로 주어지는 배열 hider_positions의 크기는 9이다. $i$번째 원소는 $i$번째 숨은 사람의 좌표를 나타낸다. (단, $0 \leq i \leq 8$)
• 이 함수는 $200 \times 200$ 크기의 2차원 배열을 반환해야 한다. $i$번째 배열의 $j$번째 원소는 정령이 $(i,j)$ 좌표에 표시할 값을 의미하며 이 값은 $1$ 이상 $24$ 이하여야 한다. 

vector<int> play_semia()

• 이 함수는 Find 함수를 최대 1번, Get 함수를 최대 4번 호출할 수 있다.
• 이 함수는 길이 9의 배열을 반환한다. 반환하는 배열의 $i$번째 값은 $i$번 사람이 숨어있는 사분면 번호이다.

제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다. 각 테스트 케이스에 대해, 위의 함수를 호출하는 프로그램은 다음과 같이 정확히 두 번 실행된다.

프로그램이 첫 번째로 실행될 때는 다음과 같다.

• play_spirit 함수가  호출된다.
• play_spirit 함수의 실행 결과가 채점 시스템에 저장된다.
• play_semia 함수는 호출되지 않는다.

프로그램이 두 번째로 실행될 때는 다음과 같다.

• play_semia 함수가 호출된다. 
• play_semia 함수가 호출하는 Find 함수와 Get 함수의 반환 값은 play_spirit의 앞선 실행 결과에 의존한다.
• play_spirit 함수는 호출되지 않는다.

이 문제에서 프로그램의 실행 시간과 메모리 사용량은 두 번의 실행을 합하여 계산된다.

Sample Grader

 

Sample Grader는 두 번의 실행에서 다음과 같이 입출력을 수행한다. Sample grader를 포함한 파일은 providing.zip 에서 내려받을 수 있다.

여러분의 코드를 sol_template.cpp에 작성한 후 로컬 환경에서 컴파일해볼 수 있다.

첫 번째 실행에서는 다음과 같이 입력을 받는다.

• Line 1: Semia의 위치를 나타내는 두 정수
• Line 2-10: 친구들의 위치를 나타내는 두 정수

첫 번째 실행의 출력이자, 두 번째 실행의 입력은 다음과 같다.

• Line 1-200: 정령이 각 격자칸에 적은 정수
• Line 201: Semia의 위치를 나타내는 두 정수

두 번째 실행에서 Sample grader는 play_semia함수의 출력값을 한 줄에 공백으로 구분하여 출력한다.