波音公司的事故处理小组刚刚接到一条命令:搜索一架坠毁飞机的黑匣子。当他们赶到事故现场时发现黑匣子的探测器电池中的电量不足。由于时间紧迫,他们只能用电池中余下的电力探测黑匣子。
已知黑匣子可能隐藏在n个地点,这些点是由n-1条连接两点的边连接起来的(a tree?!)。小组的组长HarryPotter使出了看家本领,他声称能在任意一个地点使用探测器找到黑匣子所在方向。也就是说假设HarryPotter站在A点,他能够找出点B,满足A与B直接相连(或A与B相同),并且A点到黑匣子所在点的最短路径包含B(就是说没有重复节点的路径啦。)。但是HarryPotter每次探测黑匣子的方向需要1分钟,而探测器中的电池只能供应15分钟电力。请你帮助这个小组找到黑匣子,并且使用探测器的次数不超过15次。
一个成功的交互例子
b.in:
3 3
1 2
2 3
Pascal:
uses b_lib;
var
b,i,j,datn:longint;
begin
datn:=getn; //datn=3
getroad(i,j); //i=1,j=2
getroad(i,j); //i=2,j=3
b:=explore(2); //b=3
b:=explore(3); //程序自动退出,交互成功
end.
c/c++:
#include "b_lib.h"
int b,i,j,datn;
int main()
{
datn=getn(); //datn=3
getroad(&i,&j); //i=1,j=2
getroad(&i,&j); //i=2,j=3
b=explore(2); //b=3
b=explore(3); //程序自动退出,交互成功
return 0; //此语句不会被执行
}
评分标准
如果程序在时限内调用函数explore(m)并自动退出则可得该数据的满分,
否则得0分。
其中m为黑匣子所在地点编号。
如何调试
将b_lib.pas或b_lib.h放在程序所在目录下。
在程序所在目录建立输入文件b.in。
文件第一行是整数n,m。n为地点数目,m为黑匣子所在地点编号。
以下有n-1行,每行有两个整数i,j表示有一条道路连接地点i与地点j。
注意事项
1.评测时b.in的数据格式与此不同。
2.程序不得读写任何文件或标准输入输出。
3.题目连接中的交互式库在n<=1000的条件下占用时间不超过0.5s。
评测时的交互库在n<=10000的条件下占用时间不超过0.1s。
4.调试时最好不要使用交互库中出现过的变量名。