【QED】原始部落的试验

本文主要是介绍【QED】原始部落的试验，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

注：这是一道交互题。

公元前2077年，X部落的酋长正在谋划升级改造他们的投石车。现用的投石车杀伤力实在太弱，他希望换用更大的石头，以确保在部落冲突中能够击毁敌方的城墙。

根据"力大砖飞"的信仰，他坚信，石头体积越大，杀伤力越强；若是使用大小为 $10^6$ 的石头，则必然能够摧毁敌方城墙。然而，为了节约成本，他又希望使用的石头体积尽可能地小。

现在他将这个问题交给了作为部落研发主管的你，你需要通过试验替他找出，在能够摧毁敌方城墙的前提下，可以选用的石头体积最小为多少？由于研发经费有限，你只能进行最多 $24$ 次试验。你需要在若干次试验后，向酋长提交你的答案。

由于原始部落加工精度有限，你只能选用体积大小为正整数的石头，因此，你也只需将答案精确到个位数即可。

交互格式

这是一道交互题。请务必在每次输出后$\text{换行}$并$\text{刷新输出缓冲区}$。刷新缓冲区的一种可行代码将会在题目末尾给出。

你需要以? x的格式输出，以代表选用大小为 $x$ 的石头进行一次试验。你需要确保每次试验的 $x$ 是正整数且满足 $1\le x\le 10^6$，你最多能够进行 $24$ 次这样的输出。

紧随其后，你需要从标准输入中读入一个字符串。该字符串代表了本次试验的结果，它只可能是Failed或Succeeded。前者代表大小为$x$的石头未能摧毁敌方城墙，后者代表大小为$x$的石头成功摧毁了敌方城墙。

在你认为能够确认答案后，你可以随时以! x的格式输出。其中 $x$ 代表你的答案，即在能够摧毁敌方城墙的前提下，可以选用的最小石头体积。该次输出后不会有任何输入，你务必在该次输出后立即结束你的程序。

测试样例

FailedFailedFailedFailedFailedFailedFailedFailedFailedFailedFailedFailedFailedFailedFailedFailedFailedFailedFailedSucceededSucceededSucceededSucceededSucceeded

? 1? 2? 3? 4? 5? 6? 7? 8? 9? 10? 11? 12? 13? 14? 15? 16? 17? 18? 19? 20? 21? 22? 23? 24! 20

样例说明

设最终答案为 $ans$，上述样例展示了 $ans=20$ 时一种可行的交互示例，仅作展示输入输出格式用，并不代表正确的解题思路。

题目保证最终答案 $ans$ 满足 $1\le ans\le 10^6$。

附录

请务必在每次输出后换行并刷新输出缓冲区，否则可能会出现错误。

各语言中刷新输出缓冲区的代码语句如下：

• 对于 C：fflush(stdout);
• 对于 C++：std::cout<<std::flush;
• 对于 Java：System.out.flush();
• 对于 Python：

  import sys           #在源代码首行添加此语句
  sys.stdout.flush()   #在需要刷新缓冲区时使用
  

思路

这道题目就是要一个经典的二分查找，只不过是一个交互类型的题目，注意每一次输出之后一定要输入对应的语句刷新缓冲区

核心代码

void solve()
{int left=1,right=1e6;string s;while(left<right){int mid=(left+right)>>1;printf("? %d\n",mid);std::cout<<std::flush;cin>>s;if(s[0]=='S')right=mid;else if(s[0]=='F')left=mid+1;}cout<<"! "<<left<<endl;
}

这篇关于【QED】原始部落的试验的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---