问题 4622 --2.Search

4622: 2.Search

题目描述

      波音公司的事故处理小组刚刚接到一条命令:搜索一架坠毁飞机的黑匣子。当他们赶到事故现场时发现黑匣子的探测器电池中的电量不足。由于时间紧迫,他们只能用电池中余下的电力探测黑匣子。
    已知黑匣子可能隐藏在n个地点,这些点是由n-1条连接两点的边连接起来的(a tree?!)。小组的组长HarryPotter使出了看家本领,他声称能在任意一个地点使用探测器找到黑匣子所在方向。也就是说假设HarryPotter站在A点,他能够找出点B,满足A与B直接相连(或A与B相同),并且A点到黑匣子所在点的最短路径包含B(就是说没有重复节点的路径啦。)。但是HarryPotter每次探测黑匣子的方向需要1分钟,而探测器中的电池只能供应15分钟电力。请你帮助这个小组找到黑匣子,并且使用探测器的次数不超过15次。

输入

  程序需要在头部添加如下代码:
  uses b_lib;
  该函数库提供如下函数:
  function getn:longint;
  procedure getroad(var i,j:longint);
  function explore(i:longint):longint;

c/c++: b_lib.h
  程序需要在头部添加如下代码:
  #include "b_lib.h"
  该函数库提供如下函数:
  int getn();
  void getroad(int * i,int * j);
  int explore(int i);

    程序首先需要调用函数getn(),它返回地点总数n。然后调用n-1次函数getroad(i,j),每次返回的整数i,j表示地点i与地点j间有一条路,每次返回的i与j表示的道路均不相同。之后程序可以调用函数explore(A),它返回HarryPotter在地点A使用探测器找到的黑匣子所在方向(如果A<1或A>n,交互库会自动退出),如果A点就是黑匣子所在地,那么程序会自动退出,否则函数返回整数B(A,B含义如题所述)。注意如果程序第15次调用函数explore(a)并且A不是黑匣子所在地,那么程序也会自动退出。

限制:0<n<=10000;0<i,j,A,B<=n

输出

样例输入输出

输入#1 复制
输出#1 复制

提示

一个成功的交互例子

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.调试时最好不要使用交互库中出现过的变量名。

序号 标题 作者 发表时间 费用 订购数 操作