UOJ Logo Universal Online Judge

UOJ

#517. 【美团杯2020测试赛】交互测试

附件下载 统计

因为正式赛有一道交互题,所以在这儿,先让大家熟悉一下交互题的做题方式。

任务

你需要编写一个函数 find_pos,来找到一个隐藏的单调不降的有序数组中,小于等于某一个数字的数有多少个。

  • find_pos(n, x)
    • n: 有序数组的长度。
    • x: 你的目标是计算小于等于 x 的数的个数。

你可以调用函数 query 以帮助你确定答案。我们会根据你调用这个函数的次数评分。

  • query(i) 接受一个 $[1,n]$ 中的整数,并返回有序数组中第 $i$ 个数的值。

在一组测试数据中,find_pos 只会被调用一次。

实现细节

本题只支持 C++。

你只能提交一个源文件实现如上所述的 find_pos 函数,并且遵循下面的命名和接口。

C/C++

你需要包含头文件 find.h

int find_pos(int n, int x);

你需要把答案以返回值的形式返回。

函数 query 的接口信息如下。

int query(int i);

注意 $i$ 的值必须在 $[1,n]$ 中。该函数的返回值是有序数组中第 $i$ 个数,即第 $i$ 小的数。

如果有不清楚的地方,见样例及测评库下载,内附了样例程序

评测方式

评测系统将读入如下格式的输入数据:

  1. 第 $1$ 行: $n, x$,表示有序数组长度以及询问的数字 $x$。
  2. 第 $2$ 行: $n$ 个空格隔开的整数,表示输入的有序数组。

find_pos 返回后,评测系统将输出你的答案以及 query 的调用次数。

样例输入

样例一

input

5 3
1 2 3 3 4

output

4 5

explanation

样例输出的含义为 find_pos 在 $5$ 次询问之后,返回了答案 $4$。

限制与约定

find_pos 只能进行不超过 $20$ 次询问。如果超过了这个询问数量,你的程序将无法得分,

输入保证有序数组中的所有元素以及 $x$ 都是 $[1, 10^9]$ 中的整数。

Small Task: $n \leq 20$

Large Task: $n \leq 10^5$

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例交互库下载