#P2034. 弦论
弦论
Problem Description
本题为交互题,请确保你已经完成了交互题测试或了解交互题怎么做,监考人员不会回答任何关于如何做交互题的问题
kuro最近在学习巧克力物理学课程时,老师在解释弦论(String theotry)的相关内容时,提到了下面这个问题。
有个隐藏的字符串,仅由小写英文字母组成,总长为,每次操作你可以进行一次询问,询问某个字符串在所有隐藏的字符串中作为前缀共出现了多少次,你可以进行最多次交互,最后,你需要回答最长的字符串是什么(回答的次数不计入询问次数,如果有多个答案,你可以选择任何一种作为回答)。
根据惯例,kuro应该不会这个问题,会来求助你。
如果我们说一个长度为的字符串是另一个字符串的前缀,那么应该满足的长度小于或等于的长度,且对于所有的,.
Input Format
第一行为两个整数,表示字符串数量和字符串总长。
交互
要进行询问,请按以下格式输出一行(不含引号)
"? s"
代表你需要询问的串,注意,s的长度应不大于200!
此时会输入一个整数,代表在所有隐藏的字符串中作为前缀串共出现的次数.
要回答答案,请按以下格式输出一行(不含引号),如果有多个答案,你可以选择任何一种作为回答。
"! s"
代表你的答案,注意,s的长度应不大于200!
此时会输入一个整数,若,你的回答正确;若,你的回答错误.
若在任何时候输入的数为-1,说明你的询问超出次数/询问不合法/回答不合法/答案错误/其他输入错误,此时,你需要直接退出程序,接收到Wrong Answer。否则,你可能会得到任意一种错误类型作为回应
输出询问或回答后,不要忘记输出换行并刷新缓存区。否则,您可能会收到 Time limit exceeded 判定。为此,请使用:
在 C++ 中 fflush(stdout)或 cout.flush()
在 Java 中 System.out.flush()
在 Pascal 中 flush(output)
在 Python 中 stdout.flush()
对于其他语言,请参阅其他语言的文档。
交互器不是自适应的,这意味着在参与者提出查询之前就有确定答案,并且不依赖于参与者提出的询问。
Output Format
Sample
注意:双斜杠表示注释,双斜杠后的内容实际上并不会输入,你也不需要输出
输入 #1
3 9//字符串个数 总长度
3//第一次回答
2//第二次回答
1//答案正确
输出 #1
? a//第一次询问
? aa//第二次询问
! aba//回答答案,也可以回答aaa或aab
隐藏的字符串为"aaa","aba"和"aab"
输入 #2
4 10//字符串个数 总长度
4//第一次回答
3//第二次回答
2//第三次回答
1//第四次回答
1//答案正确
输出 #2
? a//第一次询问
? aa//第二次询问
? aaa//第三次询问
? aaaa//第四次询问
! aaaa//回答答案
隐藏的字符串为"a","aa","aaa"和"aaaa"