luogu#P8494. [IOI2022] 最罕见的昆虫
[IOI2022] 最罕见的昆虫
题目背景
滥用评测资源者封号
本题为交互题。
您不需要也不应该在提交的程序中包含 insects.h
头文件和主函数。
但是在您的程序中,需要声明以下三个函数:
void move_inside(int i);
void move_outside(int i);
int press_button();
例如,您的程序可以是这样:
#include <bits/stdc++.h>
using namespace std;
void move_inside(int i);
void move_outside(int i);
int press_button();
int min_cardinality(int N) {
// Code Here
}
题目描述
Pak Blangkon 的房子四周有 只昆虫,编号为 至 。每只昆虫有一个类型,以从 至 (包含 和 )的整数编号。可能有多只昆虫类型相同。
假设将昆虫按照类型分组。我们定义最常见昆虫类型的基数是昆虫最多的分组中的昆虫数。类似地,最罕见昆虫类型的基数是昆虫最少的分组中的昆虫数。
例如,假设有 只昆虫,类型分别为 。在此情形中,最常见昆虫类型的基数是 ,是因为类型 和类型 的分组均有最多数目的昆虫,每个分组都有 只。最罕见昆虫类型的基数是 ,是因为类型 、类型 和类型 的分组均有最少数目的昆虫,每个分组都有 只。
Pak Blangkon 不知道这些昆虫的类型。他有一台单按钮的机器,可以提供昆虫类型相关的信息。刚开始时,机器是空的。在使用机器时,可以做如下三种操作:
- 将一只昆虫放进机器。
- 将一只昆虫取出机器。
- 按下机器的按钮。
每种操作最多可以做 次。
每当按下按钮时,机器会报告在机器内的最常见昆虫类型的基数。
你的任务是使用上述机器,确定 Pak Blangkon 的房子四周所有 只昆虫中最罕见昆虫类型的基数。此外,在某些子任务里,你的得分取决于机器执行某种操作的最大次数(详见子任务一节)。
输入格式
你要实现以下函数:
int min_cardinality(int N)
- :昆虫数量。
- 此函数应返回 Pak Blangkon 的房子四周所有 只昆虫中最罕见昆虫类型的基数。
- 此函数恰好被调用一次。
该函数可调用以下几个函数:
void move_inside(int i)
- :将被放进机器的昆虫编号。编号 的取值范围是 至 (包含 和 )。
- 如果昆虫已在机器内,函数调用不会影响机器内昆虫的集合。但是,调用仍会被计入此类操作的次数。
- 此函数最多可以被调用 次。
void move_outside(int i)
- :将被从机器中取出的昆虫编号。编号 的取值范围是 至 (包含 和 )。
- 如果昆虫已在机器外,函数调用不会影响机器内昆虫的集合。但是,调用仍会被计入此类操作的次数。
- 此函数最多可以被调用 次。
int press_button()
- 此函数返回机器内最常见昆虫类型的基数。
- 此函数最多可以被调用 次。
- 评测程序不是适应性的。也就是说,所有 只昆虫的类型在
min_cardinality
调用前已经确定。
输出格式
考虑在某个场景下,有 只类型分别为 的昆虫。
函数 min_cardinality
的调用方式如下:
min_cardinality(6)
此函数按以下次序调用了 move_inside
、move_outside
和 press_button
。
函数调用 | 返回值 | 机器内的昆虫 | 机器内的昆虫类型 |
---|---|---|---|
move_inside(0) |
|||
press_button() |
|||
move_inside(1) |
|||
press_button() |
|||
move_inside(3) |
|||
press_button() |
|||
move_inside(2) |
|||
move_inside(4) |
|||
move_inside(5) |
|||
press_button() |
|||
move_inside(5) |
|||
press_button() |
|||
move_outside(5) |
|||
press_button() |
至此,已有充分信息表明,最罕见昆虫类型的基数是 。
因此,函数 min_cardinality
应返回 。
在这个例子里,move_inside
被调用 次,move_outside
被调用 次,press_button
被调用 次。
提示
约束条件
- 。
子任务
- (10 分) ;
- (15 分) ;
- (75 分) 没有额外的约束条件。
如果在某个测试用例上,函数 move_inside
、move_outside
或 press_button
的调用次数不符合“实现细节”中给出的约束条件,或者 min_cardinality
的返回值不正确,你的解答在此子任务上得分为 。
令 为以下三个值的 最大值:move_inside
的调用次数、move_outside
的调用次数、press_button
的调用次数。
在子任务 3 中,你可能会得部分分。令 为此子任务所有测试用例的 的最大值。你在此子任务的得分将根据以下表格计算:
条件 | 得分 |
---|---|
(CMS 报告“Output isn’t correct ”) |
|
评测程序示例
令 是长度为 的整数数组,其中 是编号为 的昆虫的类型。
评测程序示例按以下格式读取输入:
- 第 行:;
- 第 行:。
如果评测程序示例检测到非法行为,评测程序示例将输出 Protocol Violation: <MSG>
,其中 <MSG>
为如下某种类型:
invalid parameter
:在函数调用move_inside
或move_outside
时,参数 的值不在 至 的范围内(包括 和 )。too many calls
:函数move_inside
、move_outside
或press_button
中某个的调用次数超过 次。
否则,评测程序示例按以下格式输出:
- 第 行:
min_cardinality
的返回值; - 第 行:。
约定
题面在给出函数接口时,会使用一般性的类型名称 void
、bool
、int
、int[]
(数组)和 union(bool, int[])
。
在 C++ 中,评测程序会采用适当的数据类型或实现,如下表所示:
void |
bool |
int |
int[] |
---|---|---|---|
void |
bool |
int |
std::vector<int> |
union(bool, int[]) |
数组 a 的长度 |
---|---|
std::variant<bool, std::vector<int>> |
a.size() |
C++ 语言里,std::variant
定义在 <variant>
头文件中。
一个返回类型为 std::variant<bool, std::vector<int>>
的函数可以返回一个 bool
或一个 std::vector<int>
。
以下示例代码给出了三个返回 std::variant
的函数,它们都能正常工作:
std::variant<bool, std::vector<int>> foo(int N) {
return N % 2 == 0;
}
std::variant<bool, std::vector<int>> goo(int N) {
return std::vector<int>(N, 0);
}
std::variant<bool, std::vector<int>> hoo(int N) {
if (N % 2 == 0) {
return false;
}
return std::vector<int>(N, 0);
}