시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 94 | 27 | 19 | 22.892% |
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명이 각각 자신을 원점으로 하는 사분면 중 어디에 속해있는지 구하려고 한다. 사분면은 아래와 같이 번호를 붙인다.
Semia와 정령을 도와 두 명의 전략을 구현해보자!
Grader에서 기본으로 제공하는 함수는 다음과 같다. 여러분은 이 함수들을 적절히 호출하여 문제를 해결해야 한다.
pair<int, int> Find(int x)
int Get(int x, int y)
여러분은 다음 두 함수를 구현해야 한다.
vector< vector<int> > play_spirit(vector< pair<int, int> > &hider_positions)
vector<int> play_semia()
Find
함수를 최대 1번, Get
함수를 최대 4번 호출할 수 있다.제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다. 각 테스트 케이스에 대해, 위의 함수를 호출하는 프로그램은 다음과 같이 정확히 두 번 실행된다.
프로그램이 첫 번째로 실행될 때는 다음과 같다.
play_spirit
함수가 호출된다.play_spirit
함수의 실행 결과가 채점 시스템에 저장된다.play_semia
함수는 호출되지 않는다.프로그램이 두 번째로 실행될 때는 다음과 같다.
play_semia
함수가 호출된다. play_semia
함수가 호출하는 Find
함수와 Get
함수의 반환 값은 play_spirit
의 앞선 실행 결과에 의존한다.play_spirit
함수는 호출되지 않는다.이 문제에서 프로그램의 실행 시간과 메모리 사용량은 두 번의 실행을 합하여 계산된다.
Sample Grader는 두 번의 실행에서 다음과 같이 입출력을 수행한다. Sample grader를 포함한 파일은 providing.zip 에서 내려받을 수 있다.
여러분의 코드를 sol_template.cpp에 작성한 후 로컬 환경에서 컴파일해볼 수 있다.
첫 번째 실행에서는 다음과 같이 입력을 받는다.
첫 번째 실행의 출력이자, 두 번째 실행의 입력은 다음과 같다.
두 번째 실행에서 Sample grader는 play_semia
함수의 출력값을 한 줄에 공백으로 구분하여 출력한다.
100 100 1 1 1 2 1 3 150 150 150 1 150 2 190 190 2 150 1 190
3 3 3 1 4 4 1 2 2
9명의 위치가 각각 (1,1), (1,2), (1,3), (150,150), (150,1), (150,2), (190,190), (2,150), (1,190)
인 경우를 생각해보자.
그레이더는 다음 함수를 호출한다.
vector< vector
play_spirit
은 200×200 크기의 배열을 반환해야 한다.
이후 그레이더는 play_semia
함수를 호출한다. 만약 Semia의 위치가 (100,100)
이었다면 이 함수는 배열 [3,3,3,1,4,4,1,2,2]
를 반환해야 한다.
입출력 예제는 Sample Grader가 해당 케이스에서 수행하는 입출력 형식을 따르며, 실제 채점 시스템과는 다르게 구현되어 있을 수 있다.
Contest > BOJ User Contest > Semi-Game Cup > Semi-Game Cup 3 H번
C++17, C++11, C++14, C++20, C++11 (Clang), C++14 (Clang), C++17 (Clang), C++20 (Clang)