这是一道交互题。
有一个长度为 的隐藏序列 。每个元素都是 、 或 ,且三个值都至少出现一次。
攻击者最多可以进行 次比较。每次选择两个不同的位置 ,询问 与 的大小关系。防守者回答小于、等于或大于。防守者无需提前确定序列,可以根据之前的询问自适应地回答,但始终必须存在至少一个与所有已有回答一致的合法序列。
如果攻击者能仅根据比较结果唯一确定序列,则攻击者获胜。如果最多 次比较后仍有至少两个可能的序列,则防守者获胜。单纯猜测序列不算攻击者获胜。
给定 ,选择具有必胜策略的角色并执行策略,对手由评测程序扮演。你的策略必须保证在对手的所有合法行为下获胜。
选择防守者时,结束后必须提交两个不同且与所有回答一致的合法序列。
首先按以下格式给出整数 :
每次运行只有一局游戏。后续输入取决于所选角色,并遵循下述交互协议。
选择角色
第一行输出 A 表示攻击者,或输出 D 表示防守者。若所选角色无法保证在对手的所有合法行为下获胜,则判为答案错误。
攻击者 按以下格式输出比较询问:
?
必须满足 且 。当 、、 时,评测程序分别返回 、、。可以重复询问同一对位置,但每次都计入次数。最多进行 次询问。
这是选择攻击者的交互示例,回答唯一确定序列为 。样例输入按顺序列出评测程序的消息,样例输出列出选手的消息,实际运行时需要交替通信。
这是选择防守者的交互示例。两个证据 和 都满足第一个元素小于第二个、第二个大于第三个。实际询问可能与样例不同。
-101唯一确定序列后,按以下格式输出并立即结束程序:
!
输出的序列必须是与所有已有回答一致的唯一合法序列。如果还存在其他可能序列,则判为答案错误。
防守者 评测程序最多发送 条以下格式的询问:
?
对每条询问输出 -1、0 或 1,分别表示 、 或 。必须始终保留至少一个与所有回答一致的合法序列。
评测程序发送单独的 ! 时,询问结束。评测程序也可能在不足 次时结束询问。按以下格式输出两个不同的序列 ,然后立即结束程序:
!
两个序列均须长度为 ,仅包含 、、,并且每个值都至少出现一次。它们至少在一个位置上不同,且都必须与之前的所有回答一致。
每次输出后都必须刷新缓冲区。 超过询问次数、使用非法位置或符号、给出矛盾回答或错误的最终输出,均可能导致答案错误。不刷新缓冲区或在没有后续输入时等待,可能导致超时。遇到输入结束时应立即退出;最终输出后不要等待额外输入。符号之间的连续空白及最后是否有换行不影响判定。