UOJ Logo Universal Online Judge

UOJ

#254. 【Rujia Liu's Present 7】Explore the dune

附件下载 统计

根据新出土的一批史料记载,在塔克拉玛干沙漠中的一座沙丘下面,埋藏着一个神秘的地下迷宫。由著名探险家阿强率领的探险队经过不懈的挖掘,终于发现了通往地下迷宫的入口!队员们兴奋不已,急忙钻下去,去寻找那个埋藏已久的秘密。

他们刚钻进迷宫,只听“轰隆”一声巨响,回头一看,入口已与石墙融为一体,无法辨认。他们意识到自己被困在迷宫里了!环顾周围,似乎是一个洞穴。

这座迷宫由很多洞穴组成,某些洞穴之间有道路连接。每个洞穴都有一盏灯,凭借着微弱的灯光,可以看清有多少条道路与这个洞穴相连。每个洞穴的内部是完全相同的,且无法做标记。每条道路也是完全相同的,也无法做标记。

阿强凭借着微弱的灯光,发现了墙壁上的一段文字(事实上,每个洞穴的墙壁上都有这段文字),翻译成现代汉语就是:“陌生人,请把这个迷宫的洞穴数和道路数告诉我,我就会指引你走出迷宫。”

阿强很快镇定了下来,他拿出一个路标,对队员们说:“这个迷宫的危险程度远超出我们的想象,为了安全起见,大家一定要集体行动。我这儿有一个路标,有了它,我们一定能探明迷宫的结构。大家跟我走!”

现在,轮到你扮演阿强了。路标只有一个,可以随身携带,也可以暂时放在某个洞穴中(把路标放在道路上是毫无意义的,因为那里一片漆黑,什么都看不见)。你的任务很简单:用尽量少的步数探明这个迷宫共有多少个洞穴和多少条道路。“一步”是指从一个洞穴走到另一个相邻的洞穴。

交互格式

本题是一道交互式试题,你的程序需要和交互程序通过标准输入输出进行交互。每次向标准输出打印了一行后,请立即刷新缓冲区

对于每个测试点,交互库首先给出一行一个整数 $T$ 表示测试数据组数。

对于每组测试数据:

你可以通过输出若干操作来和交互库交互,具体的操作如下:

  1. Look,表示你观察四周。
    • 交互库会输出一行两个整数 $d,s$,其中 $d$ 表示当前洞穴连接道路条数,$s=0$ 表示当前洞穴没有路标,$s=1$ 表示当前洞穴有路标。
  2. Walk i,其中 $i$ 是一个整数,表示走过当前洞穴连接着的道路 $i$。初始时洞穴连接的道路逆时针编号 $0,1,\cdots,d-1$,随机起点,而之后的每个洞穴以同样方式编号,但是保证道路 $0$ 是来时的道路,即除了第一次 Walk 操作,保证 Walk 0 是返回。
    • 交互库不会返回任何信息。
  3. Put 将路标放置在当前洞穴,你需要保证路标在身上。
    • 交互库不会返回任何信息。
  4. Take 表示将当前洞穴的路标拿起,你需要保证当前洞穴有路标。
    • 交互库不会返回任何信息。
  5. Answer n m,表示你认为这个迷宫有 $n$ 个洞穴和 $m$ 条道路。
    • 交互库不会返回任何信息,并将结束这组数据的评测。

对于每组测试数据,你至多使用 $65536$ 次 Walk 操作。

样例

交互库输出 选手程序输出
1 $~$
$~$ Look
3 0 $~$
$~$ Put
$~$ Walk 0
$~$ Look
2 0 $~$
$~$ Walk 1
$~$ Look
2 0 $~$
$~$ Walk 1
$~$ Look
3 1 $~$
$~$ Take
$~$ Walk 1
$~$ Look
2 0 $~$
$~$ Walk 1
$~$ Look
1 0 $~$
$~$ Answer 5 5

explanation

迷宫如图:

样例图片

数据范围与提示

设 $n$ 是洞穴个数,$m$ 是道路条数。

本题只有一个测试点,保证 $1\leq T\leq 25, 2\leq n\leq 25, 1\leq m\leq 300$,迷宫联通,没有自环和重边。

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

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

来源

Uva Online Judge,NOI2004,题目作者刘汝佳,贝小辉。

特别鸣谢:各位验题人, Md. Mahbubul Hasan