#1445. 「2021 营员交流」探险

「2021 营员交流」探险

题目描述

这是一道交互题

某天,你在小明埋在地下的宝藏屋中探险。

小明的宝藏屋呈一个无限满二叉树的结构,其中根节点与地面相连,如下图所示:

二叉树

不知怎么的,你突然迷路了。好在小明考虑到了这点,于是它在你探险之前给了你一个探测器,它能给你得到你离地面的相对高度 (即当前宝藏屋的深度,其中地面的深度为 00),不过它的电量已经不足,因此至多只能使用 TT 次。

由于每个宝藏屋都有恰好 33 条道路连接它,故小明为了方便起见,把与每个宝藏屋相邻的三条道路分别编号为 0,1,20, 1, 2

目前你只知道你当前离地面的相对高度,你需要编写一套寻路系统来到达地面。注意你现在的食物和水分只够你移动 10500001050000 次。

任务

你需要编写一个函数 explore,来模拟寻路的过程:

  • explore(n, T):
    • n 表示你当前所在宝藏屋的深度。
    • T 表示你能使用探测器的次数上限。
    • 函数不需要返回值,当你到达地面时,请立即退出函数。

你可以调用两个函数 move 和 query 来完成寻路:

  • move(type):
    • type 表示你所选的道路的编号。
    • 调用此函数后会从当前结点沿着编号为 type 的道路进行一次移动。
    • 函数返回一个 bool,表示移动后是否到达地面。
  • query():
    • 函数返回一个 int,表示当前你离地面的相对高度。

实现细节

本题只支持 C++。

你只能提交一个源文件实现如上所述的 explore 函数,并且遵循下面的命名和接口。你需要包含头文件 explore.h

void explore(int n, int T);

函数 move, query 的接口信息如下。

bool move(int type);
int query();

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

评测方式

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

第一行包含两个整数 n,Tn, T,意义同 explore 函数。

第二行包含一个长度为 nn 的仅由 0,1,2\texttt 0, \texttt 1, \texttt 2 组成的字符串,表示地面与你所在的宝藏屋的连线中,(从浅到深) 每条道路的编号,保证相邻两个字符不同。

如果 explore 正常返回且到达地面,评测系统将分别输出你调用 move 和 query 的次数,否则返回一条错误信息,有如下几种形式:

  1. move: too many calls [more than 1050000] 调用 move 的次数超过 10500001050000
  2. move: already at the ground 已经到达地面却仍在调用 move 函数;
  3. move: type [equals to x] not in [0, 2] 调用 move 的参数 type 等于 xx,不为 {0,1,2}\{0, 1, 2\} 之一;
  4. query: too many calls [more than T] 调用 query 的次数超过 TT
  5. not escaped explore 返回后未到达地面。

样例 1

3 1000
102

11 7

样例 2

见附加文件中的 ex_explore2.inex_explore2.out

数据范围与提示

本题共 1010 个测试点,每个测试点 1010 分。每个测试点的 nnTT 见下表:

测试点编号 nn TT
1 =1000= 1000 =2×109= 2 \times 10^9
2 =105= 10^5
3 =1000= 1000 =2001= 2001
4 =1024= 1024
5 =105= 10^5 =200001= 200001
6 =154000= 154000
7 =103000= 103000
8 =67000= 67000
9 =51000= 51000
10