loj#P3360. 「PA 2019」Sonda
「PA 2019」Sonda
题目描述
这是一道交互题。
有一个 个点的无向连通图。你有一个探测器,它最初在 号节点。
你每次可以向探测器发送指令,给出节点 ,如果当前节点和 之间有一条边,那么探测器就会移动到该节点,每次发出这一指令就会得到反馈信息。若探测器进行了移动并且这是探测器第偶数次移动,那么返回「成功」,否则返回「失败」。你最多可以发送 次该指令。
你还另外需要进行 次标记操作,需要保证恰好在机器人位于每个节点的时候进行一次标记操作。
交互方式
您的程序需要引用交互库:
#include "sonlib.h"
这个交互库提供以下函数:
int GetN()
- 返回一个正整数 ,表示这个图的节点数。
int GetSubtask()
- 返回一个整数 ,表示子任务类型。
- 若 ,则表示该图没有任何附加性质;
- 若 ,表示图为完整的二分图,即可以将点集划分为两非空集合 ,每个点都属于 或 中的一个,并且有 条边;
- 若 ,保证图中 与 , 与 , 与 之间一定有边;
- 若 ,保证图中所有点恰好与两个点相连。
int MoveProbe(int v)
- 向探测器发出「走向节点 」的指令,如果探测器当前就在节点 ,你的程序会被直接判为错误。若探测器进行了移动并且这是探测器第偶数次移动,那么返回
1
,否则返回0
,若探测器没有进行移动,也返回0
。
void Examine()
- 让探测器标记当前节点。如果该节点已经被标记,你的程序会被直接判为错误。当完成了所有节点的标记操作后,程序会被判定为正确并自动退出。
你需要实现主函数
int main()
样例
样例输入
4 4 0
1 2
2 3
3 1
2 4
样例交互过程
函数调用 | 返回值 | 当前探测器位置 | 成功移动次数 | 注释 |
---|---|---|---|---|
图中有 个点 | ||||
参数 | ||||
- | 标记 号点 | |||
与 之间没有边 | ||||
探测器从 移动到 ,此时探测器移动成功次数为奇数 | ||||
此时探测器移动成功次数为偶数 | ||||
- | 标记 号点 | |||
- | 标记 号点 | |||
- | - | - | 探测器已将每个点都探测一次,因此程序结束,该用例通过 |