시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 139 | 38 | 32 | 28.070% |
블랑콘씨의 집 주위를 돌아다니는 $N$ 마리의 곤충이 있고, 각각 $0$에서 $N - 1$로 번호가 매겨져 있다. 각 곤충마다 자신이 속하는 종류가 있고, $0$ 이상 $10^9$ 이하인 정수로 표현된다. 복수의 곤충이 같은 종류에 속할 수 있다.
곤충들을 종류에 따라 그룹으로 모아보기로 하자. 가장 자주 나오는 곤충 종류 그룹의 크기는 가장 많은 수의 곤충이 속하는 그룹의 곤충 수이다. 비슷하게, 가장 드문 곤충 종류 그룹의 크기는 가장 적은 수의 곤충이 속하는 그룹의 곤충 수이다.
예를 들어, $11$ 마리의 곤충이 있고, 종류가 차례로 $[5, 7, 9, 11, 11, 5, 0, 11, 9, 100, 9]$라고 하자. 이 경우, 가장 자주 나오는 곤충 종류 그룹의 크기는 $3$이다. 종류 $9$인 곤충의 그룹과 종류 $11$인 곤충의 그룹이 가장 자주 나오는 곤충 종류 그룹이며, 각각 $3$ 마리의 곤충으로 이루어져 있다. 가장 드문 곤충 종류 그룹의 크기는 $1$이다. 종류 $7$, 종류 $0$, 종류 $100$인 곤충의 그룹에는 각각 $1$ 마리의 곤충이 속한다.
블랑콘씨는 곤충의 종류를 알지 못한다. 곤충의 종류에 대한 정보를 알려주는 단추가 하나 달린 기계가 있다. 처음, 이 기계는 비어 있다. 기계를 이용하기 위해, 다음 세 가지 종류의 연산을 사용할 수 있다.
각각의 연산은 최대 $40\,000$ 번 수행될 수 있다.
단추가 눌려질 때마다, 이 기계는 현재 기계에 들어 있는 곤충들만 이용해서, 이 중 가장 자주 나오는 곤충 종류 그룹의 크기를 알려준다.
당신이 할 일은 이 기계를 사용해서 블랑콘씨 집 주위의 $N$ 마리 곤충들 중 가장 드문 곤충 종류 그룹의 크기를 구하는 것이다. 덤으로, 어떤 서브태스크에서는, 특정한 명령이 실행되는 횟수에 따라 여러분의 점수가 결정된다 (자세한 내용은 Subtasks 참고).
다음 함수를 구현해야 한다.
int min_cardinality(int N)
위 함수는 다음 함수들을 호출할 수 있다.
void move_inside(int i)
void move_outside(int i)
int press_button()
min_cardinality
함수를 호출하기 전에 이미 결정되어 있다.$6$ 마리 곤충이 있고, 종류가 차례로 $[5, 8, 9, 5, 9, 9]$인 시나리오를 생각해보자. min_cardinality
함수는 다음과 같이 호출된다.
min_cardinality(6)
이 함수는 move_inside
, move_outside
, press_button
를 다음과 같이 호출한다.
호출하는 함수 | 리턴 값 | 기계 안에 있는 곤충 | 기계 안의 곤충들 종류 |
---|---|---|---|
$\{\}$ | $[]$ | ||
move_inside(0) |
$\{0\}$ | $[5]$ | |
press_button() |
$1$ | $\{0\}$ | $[5]$ |
move_inside(1) |
$\{0, 1\}$ | $[5, 8]$ | |
press_button() |
$1$ | $\{0, 1\}$ | $[5, 8]$ |
move_inside(3) |
$\{0, 1, 3\}$ | $[5, 8, 5]$ | |
press_button() |
$2$ | $\{0, 1, 3\}$ | $[5, 8, 5]$ |
move_inside(2) |
$\{0, 1, 2, 3\}$ | $[5, 8, 9, 5]$ | |
move_inside(4) |
$\{0, 1, 2, 3, 4\}$ | $[5, 8, 9, 5, 9]$ | |
move_inside(5) |
$\{0, 1, 2, 3, 4, 5\}$ | $[5, 8, 9, 5, 9, 9]$ | |
press_button() |
$3$ | $\{0, 1, 2, 3, 4, 5\}$ | $[5, 8, 9, 5, 9, 9]$ |
move_inside(5) |
$\{0, 1, 2, 3, 4, 5\}$ | $[5, 8, 9, 5, 9, 9]$ | |
press_button() |
$3$ | $\{0, 1, 2, 3, 4, 5\}$ | $[5, 8, 9, 5, 9, 9]$ |
move_outside(5) |
$\{0, 1, 2, 3, 4\}$ | $[5, 8, 9, 5, 9]$ | |
press_button() |
$2$ | $\{0, 1, 2, 3, 4\}$ | $[5, 8, 9, 5, 9]$ |
이 시점에서, 가장 드문 곤충 종류 그룹의 크기가 $1$ 임을 아는데 충분한 정보를 얻게 된다. 따라서, min_cardinality
함수의 리턴값은 $1$이어야 한다.
이 예제에서, move_inside
함수는 $7$ 번, move_outside
함수는 $1$ 번, press_button
함수는 $6$ 번 호출되었다.
번호 | 배점 | 제한 |
---|---|---|
1 | 10 | $N \le 200$ |
2 | 15 | $N \le 1000$ |
3 | 75 | 추가적인 제약 조건이 없다. |
어떤 테스트 케이스에서든, 함수 move_inside
, move_outside
, press_button
를 호출할 때 Implementation Details에서 설명한 제약 조건을 만족하지 않았다거나, min_cardinality
함수의 출력이 틀렸다면, 해당 서브태스크에서 여러분의 점수는 $0$점이다.
$q$가 move_inside
함수 호출 횟수, move_outside
함수 호출 횟수, press_button
함수 호출 횟수 세 값 중 최대값이라고 하자.
서브태스크 3에서는 부분 점수가 있다. $m$이 이 서브태스크의 모든 테스트케이스에서 $\frac{q}{N}$의 최대값이라고 하자. 이 서브태스크에서 얻을 수 있는 점수는 다음 표에 따라 계산된다.
조건 | 점수 |
---|---|
$20 \lt m$ | $0$ (CMS에서 "Output isn’t correct "로 출력) |
$6 \lt m \le 20$ | $\frac{225}{m - 2}$ |
$3 \lt m \le 6$ | $81 - \frac{2}{3} m^2$ |
$m \le 3$ | $75$ |
$T$가 길이 $N$인 정수 배열이고 $T[i]$가 곤충 $i$의 종류라고 하자.
샘플 그레이더는 다음 양식으로 입력을 읽는다.
만약 샘플 그레이더가 프로토콜이 위반된 것을 발견하면, 샘플 그레이더는 Protocol Violation: <MSG>
를 출력하는데,<MSG>
는 다음 중 하나이다.
invalid parameter
: move_inside
또는 move_outside
를 호출할 때, $i$ 값이 $0$ 이상 $N - 1$ 이하가 아니다.too many calls
: move_inside
, move_outside
, press_button
중 어떤 한 함수가 $40\,000$ 번 초과되어 호출되었다.그 외의 경우에는, 샘플 그레이더는 다음 양식에 따라 출력한다.
min_cardinality
의 리턴값Olympiad > International Olympiad in Informatics > IOI 2022 > Day 2 5번
C++17, C++20, C++17 (Clang), C++20 (Clang)