34149번 - 거짓말쟁이 서브태스크점수언어 제한함수 구현

문제

두 친구 경곽이와 구름이는 다음과 같은 규칙의 게임을 하고 있다.

1. 양의 정수 $k$를 정한다. 이 수는 경곽이와 구름이 모두 알고 있다.
2. 구름이가 양의 정수 $n$과 $x$를 선택한 후, 경곽이에게는 $n$만 알려준다. (1ドル \leq x \leq n$)
3. 경곽이는 구름이에게 양의 정수를 원소로 가지는 집합 $S$를 하나 정해 말한다.
4. 구름이는 경곽이에게 $x$가 $S$에 속하는지 속하지 않는지 대답한다.
   • 단, 구름이는 거짓말을 할 수 있다. $x$가 $S$에 속하지 않지만 $S$에 속한다고 대답할 수 있으며, $x$가 $S$에 속하지만 속하지 않는다고 대답할 수 있다.
   • 구름이는 연속으로 최대 $k$번까지 거짓말을 할 수 있다. 즉, 연속한 $k+1$번의 질문 중 적어도 한 질문에 대한 대답은 진실임이 보장된다.
5. 경곽이가 만족할 때까지 3, 4 과정을 반복한다.
6. 경곽이는 충분한 질문 이후 양의 정수로 이루어진 집합 $S'$을 제시한다. $x$가 $S'$에 속한다면 경곽이가 승리하고, 아니라면 구름이가 승리한다.
   • 경곽이가 승리할 경우, S'의 크기가 작을수록 더 높은 점수를 받을 수 있다. 자세한 내용은 점수 부분을 참고하여라.

여러분은 경곽이가 되어 게임을 진행한다. 구름이는 이미 $k,ドル $n$ 및 $x$를 정하였다. 구름이의 거짓말을 피해 $x$가 포함된 최종 집합 $S'$을 제시해 게임에서 승리하자.

함수 목록 및 정의

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

std::vector<int> game(int k, int n)

• 이 함수는 경곽이의 역할을 하며, 구름이의 역할을 하는 그레이더와 게임을 진행한다.
• 함수의 인자로 미리 정한 $k$와 구름이가 선택한 $n$의 값이 주어진다. (1ドル \leq k \leq 6,ドル $n = 1 ,円 000$)
• 이 함수는 구름이가 설정한 $x$를 포함하는 집합 $S'$을 반환해야 한다. 반환하는 집합의 각 원소는 1ドル$ 이상 $n$ 이하이며, 집합의 크기는 $n$ 이하여야 한다. 집합에 같은 값이 여러 번 포함되어도 된다.
• 만약, 집합 $S'$에 $x$가 포함되지 않거나, 반환하는 집합의 조건을 어기는 경우 를 받는다.
• 이 함수는 하나의 테스트 케이스에 대해 단 한 번만 호출된다.

아래의 함수는 여러분이 그레이더인 구름이에게 질문을 하는 함수로, game() 함수 내에서 호출하여 사용할 수 있다.

bool ask(std::vector<int> v)

• 이 함수는 v에 $x$가 존재한다면 true를, 아니라면 false를 반환한다. 하지만, 해당 함수는 거짓말을 하여, 존재하여도 false를, 존재하지 않더라도 true를 반환할 수 있다.
• 단, 연속한 $k + 1$번의 함수 호출 중 진실을 반환한 경우가 적어도 하나 존재함이 보장된다.
• 이 함수를 최대 15ドル ,円 000$번 호출할 수 있다. 또한, 모든 호출에서 v의 크기의 총합은 1ドル ,円 000 ,円 000$ 이하여야 한다. 만약, 이를 어길 경우 를 받는다.
• 모든 호출에서 v의 각 원소는 1ドル$ 이상 $n$ 이하여야 하며, 이를 어길 경우 를 받는다. v의 원소 중 같은 값이 여러 번 포함되어도 되며, v의 크기가 0ドル$이어도 된다.

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

입력

출력

제한

서브태스크 1 (15점)

각 서브태스크의 모든 테스트 케이스에서 game이 올바르게 $x$를 포함한 집합 $S'$을 반환했다면, $S'$의 크기 $|S'|$에 따라서 점수를 얻을 수 있다.

모든 $k = 1$을 만족하는 테스트 케이스에 대해 경곽이가 게임을 승리했으며, $|S'|$가 모두 2ドル$ 이하인 경우 15ドル$점을 받을 수 있다.

서브태스크 2 (85점)

모든 테스트 케이스에 대해 경곽이가 게임을 승리한 경우 아래와 같이 점수를 받을 수 있다. $M$을 모든 테스트 케이스에서 $|S'| / 2^k$의 최댓값이라 하자.

1. $M > 20$이면, 0ドル$점을 받는다.
2. 1ドル < M \leq 20$이면, $\displaystyle 25 \times \ln \frac{20}{M}$점을 받는다.
3. $M \leq 1$이면, 85ドル$점을 받는다.

힌트

예제 1

$k = 2,ドル $n = 10,ドル $x = 5$인 경우를 생각해보자. 이는 예제를 위한 상황으로, 실제 채점 데이터에서는 $n = 1 ,円 000$인 데이터만 주어진다.

그레이더는 먼저 game 함수를 호출한다.

game(2, 10)

첫 질문으로 다음과 같은 질문을 했다고 하자.

ask({2, 3, 5, 7})

$\left\{2, ,円 3, ,円 5, ,円 7\right\}$에는 5ドル$가 포함되므로, 그레이더가 거짓말을 하지 않았다면 true를 반환해야 한다. 하지만, 그레이더는 거짓말을 하여 false를 반환했다고 하자.

두 번째 질문으로는 다음과 같은 질문을 했고, 그레이더는 거짓말을 하여 true를 반환했다고 하자.

ask({2, 4, 6, 8, 10})

그레이더는 연속으로 두 번 거짓말을 하였으므로, 다음 질문에서는 그레이더는 진실을 말하는 것이 보장된다. 다음과 같은 질문을 하였다고 하자.

ask({3, 6, 9})

그레이더는 진실인 false를 반환했다. 이후 추가적인 질문을 안 하고, $\left\{1, 5, 7\right\}$를 반환하였다. 최종적으로 5ドル$가 포함되었으므로 정답으로 인정되며, 원소의 개수는 3ドル < 2^k = 4$로 만점을 얻을 수 있다.

샘플 그레이더

첨부 부분에서 샘플 그레이더를 내려받을 수 있다.

샘플 그레이더는 아래와 같은 정보를 입력받는다.

• Line 1ドル$: $k$ $n$
• Line 2ドル$: $x$

$k,ドル $n$은 게임에서의 상수이며, $x$는 구름이가 선택한 정수이다.

샘플 그레이더는 이후 game(k, n)을 호출하여 최종적인 반환값에서 $x$가 있는지를 확인하여, 있다면 Accepted를 출력한다. 만약, 함수 호출에서의 오류 또는 최종적인 반환값에 $x$가 없다면, 샘플 그레이더는 Wrong Answer를 출력한다. 실제 그레이더는 샘플 그레이더와 다르게 ask() 함수의 반환값이 랜덤으로 결정되지 않을 수 있음에 유의하라.

첨부

• liar.zip