前言

前人之述备矣，本文旨在通过一种不那么机械神降的思维路径叙述本题的做法，希望能对于一类非传统题的做法有所帮助。

题意

这是一道交互题，你需要猜测 个数 中的最大值。保证 。

你每次可以查询 是否成立。

通过不超过 次操作确定最大值。交互库是自适应的。

思路

首先 是没有前途的，也就说我们必须得想办法把 和 两个维度一起询问。

怎么做呢？比如说斜着询问，对于 询问前 位。

我们发现这个看起来很有前途，这样我们对整个矩形询问之后可以得到一个下三角的信息，于是至少大概有个 的下界。

那么我们试着确定这个下三角形的性质以得到答案。

首先，明确不优的数字应当被删除，例如我们的信息中有 的前 与 的前 位，如果它们的前 位已经可以比较出大小了，那么其中较小的那个是可以忽略的了。

这就意味着，我们保留的下三角形每一列都应当是相同的。

以下称下三角形的最后一行为最大前缀。

为了满足这两个条件，可以用三步加入一个数：

1. 对于每个数，我们可以用一次询问其是否大于最大前缀，若是，则应当删除上一个数，直到条件不满足或者上一个数不存在；
2. 然后，我们使用一次操作询问其是否小于最大前缀，若是，则这个数应当被删除；
3. 最后，询问新的一位是 或 ，然后将该数加入下三角形。

判断一个数是否大于一个前缀，只需在给定前缀后全部补 询问。

---

完成之后，我们需要获取剩余的上三角形的信息。

由于我们一定要一次性地获取一整个后缀的信息（否则时间复杂度会变为 ），于是我们必须要询问整个前缀。

那么结果会有两个：

1. 如果对于某个数，它大于最大前缀，那么下三角形中它之后的部分都小于它，故这些数应当被删除；
2. 否则，无事发生。

这样操作结束之后，当前最大前缀一定是全局的最大前缀。

---

接下来仍然有 级别的信息，我们可以递归处理。

上界为 ，非常接近题目的要求了。

于是还需要在 中节省一步，然而现在看起来已经非常紧了，没有什么好的处理方法。

于是可以考虑放宽一些限制，我们要求整个下三角形在第二步处理之后的最大前缀是全局的最大前缀，这是我们能够向下递归的充要条件，所以这个肯定要保留。

那么第四次询问是必须的，想想前三次询问应当如何节省一步。

可以发现一个小于最大前缀的数加入下三角形之后，最大前缀并不会变化。因为在实现时，我们不能真的每次都查询最后一行的数字，而是选择一位一位地记录最大前缀，故新数前面位变小实际上不会影响最大前缀的维护。

由于查询它一定会返回小于的结果，于是它加入的这一位会被视为 ，那么接下来有两种情况：

1. 它加入的这一位有某个其它的数是 ：

   那么这个数会被这个其它的数弹掉，从而不影响我们的答案。

2. 它加入的这一位没有任何数是 ：

   于是把它保留并不影响答案，因为它对于全局的贡献恰好就只有这个 。

因为最终答案不变，故而无需判断某个数是否小于最大前缀。

那么我们就节省了一步，上界来到 。

CODE

#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
const int N=202;
int n,w;
bool res;
vector<int> a;
string s;
bool ask(int i,string s){
    cout<<i<<" "+s;
    for(int i=s.size();i<w;++i) putchar(49);
    char re[5];
    cout<<endl;
    scanf("%s",re);
    res|=re[0]=='y';
    return(re[0]=='y');
}
void solve(vector<int> a){
    if((int)s.size()==w) return;
    vector<int> b;
    for(int i=0;i<(int)a.size();++i){
        for(res=0;b.size()&&ask(a[i],s);b.pop_back()) s.pop_back();
        if((int)s.size()==w) continue;
        b.push_back(a[i]);
        s+=(res||ask(a[i],s+"0"))+48;
    }
    if(!b.size()) return;
    for(int i=b.size()-1;i;--i)
        if(ask(b[i-1],s))
            for(;i<(int)b.size();b.pop_back()) s.pop_back();
    solve(b);
}
int main(){
    scanf("%d %d",&n,&w);
    for(int i=1;i<=n;++i) a.push_back(i);
    solve(a);
    cout<<"0 "+s<<endl;
    return(0);
}