시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 2048 MB136655950.000%

문제

김동현 셰프는 자신이 오만가지 소스를 만들 수 있다고 자부한다. 과연 그럴까? 여러분은 요리 경연 대회의 심사위원이 되어서 김동현 셰프의 소스 제작 능력을 측정해 보려고 한다.

경연장에는 $N$개의 재료가 있다. 각 재료는 $0,1,\cdots,N-1$의 번호가 매겨져 있다. 김동현 셰프가 만들 수 있는 소스는 이 중 $2$가지 혹은 $3$가지의 재료들로 구성되어 있으며, 서로 다른 두 소스에 대해, 두 소스를 구성하는 재료 목록이 완전히 같을 수는 없다 (일부 재료가 겹칠 수는 있다).

수학적으로, 김동현 셰프가 만들 수 있는 소스는 집합 $X$의 원소들이다. $X$를 이루는 각 원소 $S$는 모두 $\{0,1,\cdots,N-1\}$의 부분집합이고, $|S|$는 $2$ 혹은 $3$이다. 일반적인 정의에 따라 집합은 중복 원소를 가질 수 없다.

심사위원인 당신은 김동현 셰프가 만들 수 있는 소스의 총 개수 $|X|$를 알아내야 한다. 당신에게 $X$에 대한 정보가 직접 주어지지는 않지만, 블라인드 테스트를 통해서 이에 대한 정보를 얻을 수 있다.

블라인드 테스트는 다음과 같이 진행된다.

  • 당신은 재료 $\{0,1,\cdots,N-1\}$의 부분집합 $Y$를 골라 냄비에 담아 셰프에게 줄 수 있다. 단, 냄비의 크기가 제한되어 있어 한 번에 담을 수 있는 재료의 수는 $\lceil N/2 \rceil + 1$을 넘을 수 없다. 즉, $|Y| \le \lceil N/2 \rceil + 1$이어야 한다. 이때 $\lceil t \rceil$는 실수 $t$ 이상의 정수 중 가장 작은 값을 의미한다.
  • 김동현 셰프는 자신이 냄비 $Y$ 안의 재료들만으로 만들 수 있는 소스가 총 몇 개 있는지 알려준다. 즉, 당신에게는 $f(Y)=|\{S\in X \mid S\subseteq Y\}|$가 반환된다.

당신의 목표는 적은 수의 블라인드 테스트로 $|X|$를 정확히 알아내는 것이다.

함수 목록 및 정의

다음 함수를 구현해야 한다.

int solve(int N)
  • $N$: 재료의 개수.
  • 이 함수는 $|X|$를 반환해야 한다.
  • 이 함수는 단 한 번만 호출된다.

이 함수는 다음 함수를 호출할 수 있다.

int query(vector<int> Y)
  • $Y$의 각 원소는 재료 번호를 의미한다.
  • $Y$의 각 원소는 서로 달라야 한다.
  • $0 \le Y[i] \le N-1$을 만족해야 한다. ($0 \le i \le |Y|-1$)
  • $|Y| \le \lceil N/2 \rceil + 1$을 만족해야 한다.
  • 이 함수는 $f(Y)=|\{S\in X \mid S\subseteq Y\}|$를 반환한다.
  • 이 함수는 한 테스트케이스에서 최대 $3000$번 호출할 수 있다.

제한

  • $6 \le N \le 1000$
  • $1 \le |X| \le 50\,000$
  • 모든 $S \in X$에 대해 $|S| \in \{2,3\}$
  • 이 문제에서 그레이더는 적응적(adaptive)이지 않다. 이것은 집합 $X$가 solve 호출 전 이미 정해져 있음을 의미한다.

서브태스크

번호배점제한
111

$N \le 500$, $X$의 서로 다른 두 원소 $S_i, S_j$에 대해 $S_i \cap S_j = \emptyset$, 모든 $S \in X$에 대해 $|S| = 2$

232

$N \le 500$, $X$의 서로 다른 두 원소 $S_i, S_j$에 대해 $S_i \cap S_j = \emptyset$

325

모든 $S \in X$에 대해 $|S| = 2$

432

추가적인 제약조건이 없다.

각 서브태스크에서 당신의 프로그램이 한 번이라도 $|X|$를 정확히 반환하는 데 실패하였다면, 해당 서브태스크에서 $0$점을 받는다.

당신이 특정 서브태스크의 모든 테스트케이스에 대해서 $|X|$를 정확히 반환하였다면, 서브태스크별 점수는 다음 규칙에 따라 계산한다. 각 서브태스크에 포함되는 테스트케이스에서 사용한 쿼리의 최대 수 (query 호출 횟수)를 $Q$라 하자.

서브태스크 1, 2

서브태스크 1, 2에서는 $Q \le 3000$이면 서브태스크 점수의 $100$%를 얻는다.

서브태스크 3, 4

서브태스크 3, 4에서 얻는 점수는 다음과 같이 계산한다.

  • $41 < Q \le 3000$이면 해당 서브태스크 점수에 다음 비율을 곱한 값을 얻는다. $$0.5 + \dfrac{41}{2Q}$$
  • $Q \le 41$이면 서브태스크 점수의 $100$%를 얻는다.

예제

$N = 6$이고, 김동현 셰프가 만들 수 있는 소스가 $X = \{\{0,1\}, \{2,3,4\}\}$이다. $|X| = 2$이다.

냄비의 최대 크기는 $\lceil 6/2 \rceil + 1 = 4$이다.

그레이더는 처음에 아래 함수를 호출한다.

solve(6)

참가자의 코드가 다음과 같이 상호작용할 수 있다.

query({0, 1, 2})
query({2, 3, 4})
query({0, 2, 3, 5})
  • $\{0,1\} \subseteq \{0,1,2\}$이고, $\{2,3,4\} \nsubseteq \{0,1,2\}$이므로 query({0,1,2})는 $1$을 반환한다.
  • $\{0,1\} \nsubseteq \{2,3,4\}$이고, $\{2,3,4\} \subseteq \{2,3,4\}$이므로 query({2,3,4})는 $1$을 반환한다.
  • $\{0,2,3,5\}$은 $X$의 어떤 원소도 포함하지 않으므로 query({0,2,3,5})는 $0$을 반환한다.

참가자의 코드는 solve(6)의 반환값으로 $2$를 반환하여 정답을 제출한다.

샘플 그레이더

샘플 그레이더의 입력 형식은 다음과 같다.

  • line $1$: $N$
  • line $2$: $K$ (=$|X|$)
  • 모든 $0 \le i < K$에 대해:
    • line $3+i$: $L$ $a_0$ $a_1$ $\cdots$ $a_{L-1}$
      • $2 \le L \le 3$
      • $0 \le a_j \le N-1$
      • $a_0, a_1, \cdots, a_{L-1}$은 서로 다르다.
      • $\{a_0, a_1, \cdots, a_{L-1}\}$는 집합 $X$의 원소이다.

샘플 그레이더는 여러분의 코드가 solve 함수에서 반환한 값과, query를 호출한 횟수를 다음 형식으로 출력한다.

  • line $1$: solve 함수가 반환한 값 $x$
  • line $2$: query를 호출한 횟수 $Q$

첨부

제출할 수 있는 언어

C++17, C++20, C++23, C++26, C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.