시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB138484743.119%

문제

이 문제는 함수 구현 문제입니다.

경곽이는 오랜 역사와 전통을 자랑하는 국내 최고의 박물관인 'Dinosaur Museum'의 주인이다. 경곽이는 다가오는 $K + 1$번째 겨울 시즌을 기념하여 박물관에서 축제를 개최하였다. 축제가 일어난다는 소식을 듣고 전국 각지에서 온 $N$명의 관람객들이 줄을 서 박물관에 입장하려 한다.

$3$년 만에 겨울 축제를 개최하게 된 경곽이는 박물관을 찾아주는 관람객들을 위하여 입장료 면제 이벤트를 열었다. 우선, 경곽이는 줄을 선 관람객들의 눈을 안대로 가린 후 각 사람에게 지금까지 박물관이 맞은 겨울 시즌을 상징하는 $1$번부터 $K$번까지의 모자 중 하나를 무작위로 씌워준다. 이때, 각 모자는 충분히 많으며 각 관람객에게 특정 모자를 씌워줄 확률은 모두 $\frac{1}{K}$로 동일하다. 모자를 모두 씌우고 난 후 관람객들의 안대를 회수해 각 관람객들이 자신의 모자를 제외한 다른 모든 관람객들의 모자를 확인하게 해준다. 그 후 한 명씩 임의의 순서로 박물관에 입장하면, 관람객들에게 자신이 쓰고 있는 모자의 번호인 것 같은 $1$부터 $K$까지의 수를 하나 적어 다른 관람객들이 볼 수 없게 경곽이에게 제출한다. 경곽이는 모든 관람객이 자신의 모자 종류를 정확히 적을 경우 모두의 입장료를 면제해 주고자 한다.

경곽이가 개최하는 이벤트를 들은 관람객들은 머리를 모아, 입장료를 내지 않아도 될 확률을 최대화하고자 한다. 관람객들을 도와 최선의 전략으로 관람객들이 경곽이에게 제출할 수를 알려주자.

함수 목록 및 정의

함수 구현에 앞서 #include "festival.h"를 통해 "festival.h" 헤더 파일을 포함해야 한다.

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

int answer(int N, int K, int i, std::vector<int> v);
  1. $N$은 총 관람객의 수를 의미하며, $K$는 모자 번호의 범위를 나타내는 정수이다. $i$는 관람객의 번호 나타낸다. ($2 \leq N \leq 50$; $2 \leq K \leq 9$; $1 \leq i \leq N$)
  2. $v$는 $i$번 관람객을 제외한 다른 사람들이 쓰고 있는 모자의 번호를 나타내는 길이 $N - 1$의 배열로, 각 원소는 $1$ 이상 $K$ 이하의 정수이다. 순서는 무작위이다.
  3. 이 함수는 $i$번 관람객이 쓰고 있는 모자의 번호로 예상되는 값을 반환해야 한다. 반환값은 $1$ 이상 $K$ 이하의 정수여야 하며, 그렇지 않을 경우 를 받는다.

각 입력은 독립적인 최대 $100$개의 테스트 케이스로 이루어진다. 각 테스트 케이스별로 answer 함수가 각 관람객마다 $1$번씩 총 $N$번 호출된다. answer 함수가 테스트 케이스 순서대로 호출된다는 보장은 하지 않지만, 지문에서 제시된 방식대로 동작한다는 것은 보장된다.

어떠한 테스트 케이스의 answer 함수의 반환값이 어떠한 최선의 전략의 반환값으로도 불가능한 경우 를 받는다.

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

예제

$N = 3$, $K = 2$인 경우를 생각해 보자. $1$번 관람객부터 $3$번 관람객까지 순서대로 $1$, $2$, $1$번 모자를 쓰고 있다고 가정하자.

그레이더가 첫 번째로 아래와 같은 answer 함수를 호출했다고 하자.

answer(3, 2, 1, [1, 2])

함수 인자 중 $v$는 자신을 제외한 다른 사람들이 쓰고 있는 모자의 번호를 무작위로 제공함에 유의하라. 이제 위 함수는 $1$번 관람객이 전략에 따라 적을 숫자를 반환하면 된다.

뒤이어 그레이더가 두 번째, 세 번째로 아래와 같은 answer 함수를 호출했다고 하자.

answer(3, 2, 2, [1, 1]) answer(3, 2, 3, [2, 1])

두 함수 호출은 각각 $2$번 관람객과 $3$번 관람객이 전략에 따라 적을 숫자를 반환하면 된다.

세 함수의 반환값이 각각 $1$, $2$, $1$이라면 관람객들이 입장료를 내지 않아도 된다. 반면 한 사람이라도 다르다면 관람객들은 입장료를 내야 한다. 여러분은 전략을 적절히 구성해 관람객들이 입장료를 내지 않아도 될 확률을 최대화하면 된다. 예제에서는 관람객의 순서대로 함수를 호출했지만, 실제 그레이더에서는 그렇지 않을 수 있음에 유의하라.

샘플 그레이더

Sample grader는 첫 번째 줄에 테스트 케이스의 개수 $T$를 입력받는다. 그 이후 $T$회에 걸쳐 다음과 같은 정보를 입력받는다:

  • Line $1$: $N$ $K$
  • Line $2$: $e_1 \, e_2 \, \cdots \, e_N$

$e_1, \, e_2, \, \cdots, \, e_N$는 각 관람객들이 쓴 모자의 번호를 의미한다.

Sample grader는 각 테스트 케이스에 대해 다음을 출력한다.

  • $N$, $K$, $e_i$가 범위를 만족하지 않는다면 Invalid Range를 출력한다.
  • answer 함수의 반환값이 $1$ 이상 $K$ 이하가 아니라면 Wrong Answer를 출력한다.
  • 그 외의 경우, 통과한 관람객의 수를 출력한다.

Invalid Range 또는 Wrong Answer를 출력할 시, Sample grader는 즉시 종료된다.

Sample grader는 실제 채점에서 사용하는 그레이더와 다를 수 있음에 유의하라.

첨부파일

제출할 수 있는 언어

C++17

채점 및 기타 정보

  • 예제는 채점하지 않는다.