题目背景

【不支持提交】

时间：1s
空间：1024MB

题目描述

“大奖”是一个家喻户晓的TV游戏节目。这次你很幸运地进入到最后一轮。已知编号从$0$到$n-1$的个盒子从左到右排成一行，你就站在这排盒子的前面。每个盒子里面放有一个奖品，必须打开盒子才能看到是什么奖品。已知有$v\leqslant 2$种不同类型的奖品。这$v$种类型按照奖品价值的降序从$1$到$n$排列。

类型$1$的奖品是一块钻石，价值最高。所有盒子加起来刚好只有一块钻石。类型$v$的奖品是一块棒棒糖，价值最低。为使得游戏更加激动人心，相对便宜的奖品数量远比价值昂贵的奖品数量要多。更具体一点，对于满足$2\leqslant t \leqslant v$的所有$t$，我们有： 如果类型$t-1$的奖品有$k$个，那么类型$t$的奖品将严格多于$k^2$个。

你的目标是赢得那块钻石。在游戏结束时，你必须打开一个盒子并收取盒子内的奖品。在选择要打开

的盒子之前，你可以向节目主持人Rambod提一些问题。在每一个问题中，你选择就某个$i$号盒子进行

提问。Rambod将给你一个包含两个整数的数组$a$作为回答。这两个整数的意义如下：

• 在$i$号盒子左面的盒子中，刚好有$a[0]$个盒子中的奖品，价值比$i$号盒子中的奖品价值要高。

• 在$i$号盒子右面的盒子中，刚好有$a[1]$个盒子中的奖品，价值比$i$号盒子中的奖品价值要高。

例如，假设$n=8$，在你的问题中，你选择就$i=2$号盒子进行提问。Rambod的回答是 。这个回答的意义是：

• $0$号盒子和$1$号盒子中恰好有一个盒子中的奖品比$i$号盒子中的奖品更贵。

• 在$3,4,\cdots ,7$号盒子中恰好有$2$个盒子中的奖品比$2$号盒子中的奖品更贵。

你的任务就是通过问少量的问题找出包含钻石的盒子。

实现细节

你应当实现如下函数段：

(C++) int find\_best(int n)

(Java) int find\_best(int n)

• 此函数只被测评程序调用仅$1$次。

• $n$：盒子的数量。

• 你实现的这个函数应该返回装有钻石的盒子编号，即，唯一的整数$d\ \ (0\leqslant d \leqslant n-1)$使得$d$号盒子放有类型为$1$的奖品。

上述函数可以调用下列函数

(C++) std::vector ask(int i)

(Java) int[] ask(int i)

• $i$：你在询问时选择的盒子编号。$i$的数值必须介于$0$和$n-1$之间（含）。

• 这个函数返回包含$2$个元素的数组$a$。其中，$a[0]$是在$i$号盒子的左面，奖品比$i$号盒子的奖品价值更高的盒子数目。而$a[1]$则是在$i$号盒子右面，奖品比$i$号盒子的奖品价值更高的盒子数目。

输入格式

你需要实现上述函数。

输出格式

你的函数需要返回一个合法的结果。

i = 8

3

提示

在样例中，测评工具将做如下调用：

find\_best(i)

这里有$n=8$个盒子。假定奖品类型为$[3,2,3,1,3,3,2,3]$。对函数ask的所有可能的调用以及相应的返回值列出如下：

• ask(0) 返回 $[0,3]$

• ask(1) 返回 $[0,1]$

• ask(2) 返回 $[1,2]$

• ask(3) 返回 $[0,0]$

• ask(4) 返回 $[2,1]$

• ask(5) 返回 $[2,1]$

• ask(6) 返回 $[1,0]$

• ask(7) 返回 $[3,0]$

在这个例子中, 钻石放在$3$号盒子里。所以函数find\_best应该返回$3$。

上图阐释了这个例子。图中上半部分给出了每个盒子中奖品的类型。图中的下半部分阐释了询问ask(2)。

做了标记（打√）的盒子中装有比$2$号盒子的奖品价值更高的奖品。

限制

• $3\leqslant n \leqslant 200000$.

• 每个盒子中奖品的类型介于$1$和$v$之间（含）。

• 类型$1$的奖品恰有一个。

• 对于所有$2\leqslant t \leqslant v$，如果类型$t-1$的奖品有$k$个，那么类型$t$的奖品将严格多于$k^2$个。

子任务与评分

在某些测试数据中，评测工具的行为是自适应的。这意味着在这些测试数据中评测工具并没有一个固定的奖品序列。取而代之的是，由评测工具给出的答案可能依赖于你的程序问过的问题。评测工具的回答方式可以保证，在每次回答之后，至少有一个奖品序列与到目前为止给出的所有回答都不冲突。

1. ($20$分) 恰好有$1$个钻石和$n-1$个棒棒糖 (所以，$v=2$)。你可以调用函数ask最多$10000$次。

2. ($80$分) 没有附加限制。

在子任务2中你可以获得部分分。令$q$是在这个子任务的所有测试数据上函数ask被调用的最大次数，那么你在这个子任务上的得分将按照下表计算：