#arc070d. [arc070_d]HonestOrUnkind
[arc070_d]HonestOrUnkind
题目描述
这是一个交互式的任务。
AtCoDeer鹿与个人相遇了。为方便起见,这些人被编号为至。其中,有个人是_诚实的_,剩下的个人是_不善良的_。所有这个人都知道谁是诚实的,谁是不善良的,但是AtCoDeer只知道有个诚实和个不善良的人。他试图通过向这个人提问来确定所有诚实的人。对于一个问题,AtCoDeer选择和 ,并向第个人提问以下问题:“第个人是诚实的吗?”
一个诚实的人总是正确回答“是”或“否”。然而,一个不善良的人会任意地选择“是”或“否”回答。也就是说,不善良的人使用的算法可能不是简单的算法,如总是撒谎或随机选择二分之一的概率回答。
AtCoDeer最多可以提问个问题。他会逐个提问,并在决定下一个问题时可使用前面问题的回答。
确定所有诚实的人。如果不可能确定(更正式地说,如果对于提问个问题的任何策略,都存在一种未善良人回答问题的策略,以便获得两个或更多可能的诚实人集合),报告这个事实。
约束条件
输入和输出
首先,从标准输入按照以下格式给出和:
如果不能确定诚实的人,则程序必须立即打印以下输出并终止自己:
否则,程序应该提问。每个问题必须按照以下格式写入标准输出:
?
这里,和必须是介于和(包括边界)之间的整数。对问题的回答将从标准输入按照以下格式给出:
这里,可以是Y
或N
。Y
表示“是”;N
表示“否”。
最后,答案必须按照以下格式写入标准输出:
!
这里,如果第个人是诚实的,则必须为1
,如果第个人是不善良的,则必须为0
。
判定
- **在每次输出之后,必须清空标准输出。**否则可能会导致
TLE
。 - 在打印答案后,程序必须立即终止。否则,判定器的行为是未定义的。
- 当你的输出无效或错误时,判定器的行为是未定义的(不一定给出
WA
)。
示例
以下示例中,,,答案为101
。
输入
输出
以下示例中,,,答案为Impossible
。
输入
输出