| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 2048 MB | 136 | 65 | 59 | 50.000% |
김동현 셰프는 자신이 오만가지 소스를 만들 수 있다고 자부한다. 과연 그럴까? 여러분은 요리 경연 대회의 심사위원이 되어서 김동현 셰프의 소스 제작 능력을 측정해 보려고 한다.
경연장에는 $N$개의 재료가 있다. 각 재료는 $0,1,\cdots,N-1$의 번호가 매겨져 있다. 김동현 셰프가 만들 수 있는 소스는 이 중 $2$가지 혹은 $3$가지의 재료들로 구성되어 있으며, 서로 다른 두 소스에 대해, 두 소스를 구성하는 재료 목록이 완전히 같을 수는 없다 (일부 재료가 겹칠 수는 있다).
수학적으로, 김동현 셰프가 만들 수 있는 소스는 집합 $X$의 원소들이다. $X$를 이루는 각 원소 $S$는 모두 $\{0,1,\cdots,N-1\}$의 부분집합이고, $|S|$는 $2$ 혹은 $3$이다. 일반적인 정의에 따라 집합은 중복 원소를 가질 수 없다.
심사위원인 당신은 김동현 셰프가 만들 수 있는 소스의 총 개수 $|X|$를 알아내야 한다. 당신에게 $X$에 대한 정보가 직접 주어지지는 않지만, 블라인드 테스트를 통해서 이에 대한 정보를 얻을 수 있다.
블라인드 테스트는 다음과 같이 진행된다.
당신의 목표는 적은 수의 블라인드 테스트로 $|X|$를 정확히 알아내는 것이다.
다음 함수를 구현해야 한다.
int solve(int N)
이 함수는 다음 함수를 호출할 수 있다.
int query(vector<int> Y)
solve 호출 전 이미 정해져 있음을 의미한다.| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 11 | $N \le 500$, $X$의 서로 다른 두 원소 $S_i, S_j$에 대해 $S_i \cap S_j = \emptyset$, 모든 $S \in X$에 대해 $|S| = 2$ |
| 2 | 32 | $N \le 500$, $X$의 서로 다른 두 원소 $S_i, S_j$에 대해 $S_i \cap S_j = \emptyset$ |
| 3 | 25 | 모든 $S \in X$에 대해 $|S| = 2$ |
| 4 | 32 | 추가적인 제약조건이 없다. |
각 서브태스크에서 당신의 프로그램이 한 번이라도 $|X|$를 정확히 반환하는 데 실패하였다면, 해당 서브태스크에서 $0$점을 받는다.
당신이 특정 서브태스크의 모든 테스트케이스에 대해서 $|X|$를 정확히 반환하였다면, 서브태스크별 점수는 다음 규칙에 따라 계산한다. 각 서브태스크에 포함되는 테스트케이스에서 사용한 쿼리의 최대 수 (query 호출 횟수)를 $Q$라 하자.
서브태스크 1, 2
서브태스크 1, 2에서는 $Q \le 3000$이면 서브태스크 점수의 $100$%를 얻는다.
서브태스크 3, 4
서브태스크 3, 4에서 얻는 점수는 다음과 같이 계산한다.
$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})
query({0,1,2})는 $1$을 반환한다.query({2,3,4})는 $1$을 반환한다.query({0,2,3,5})는 $0$을 반환한다.참가자의 코드는 solve(6)의 반환값으로 $2$를 반환하여 정답을 제출한다.
샘플 그레이더의 입력 형식은 다음과 같다.
샘플 그레이더는 여러분의 코드가 solve 함수에서 반환한 값과, query를 호출한 횟수를 다음 형식으로 출력한다.
solve 함수가 반환한 값 $x$query를 호출한 횟수 $Q$Olympiad > 국제정보올림피아드 대표학생 선발고사 > 2026 > 2차 선발고사 1번
C++17, C++20, C++23, C++26, C++17 (Clang), C++20 (Clang)