由于要在 $\min(n+2, \lfloor0.75×n+4 \rfloor)$ 次内答出所有的题目，因此我们要用尽量少的步数得到尽可能多道题的答案。

这里给出一种方案：

首先可以假设答案全部为 Y，这时候会得到一个数，表示这 $n$ 道题答案为 Y 的个数，不妨记为 $t$，同时记现在在第 $x$ 道题。

接下来，我们从第 $x$ 道题开始，将第 $x,x+1$ 道题的答案改为 N，然后提交答案，这时候会返回一个 $t,t+2,t-2$ 这几个数中的一个。

• 如果是 $t+2$ 或者 $t-2$ 则可以确定这两道题的答案，直接跳到第 $x+2$ 题。

• 对于 $t$ 的情况，则表示第 $x,x+1$ 道题中一道为 Y，一道为 N，我们可以把第 $x,x+1,x+2,x+3$ 道题依次改成：

• YNNN，这时候会返回一个正确题数，不妨记为 $cnt_1$，不难得到 $cnt_1$ 为 $t+1,t-1,t+3,t-3$ 中的一个。

• NYNY，这时候会返回一个正确题数，不妨记为 $cnt_2$，不难得到 $cnt_2$ 为 $t,t+2,t-2$ 中的一个。

有了这些条件后，我们可以根据以下表格得出这四道题的正确答案：

按照这样的方式，我们可以得到前面若干道题目的答案。直到剩下 $0 \sim 3$ 题后，我们就可以跳出上面的判断，接下来的 $0\sim 3$ 道题就可以通过特判通过了。不妨设还有 $m$ 题。

由于我们已经知道总共正确的题目数量，则我们可以以小于等于 $m$ 的次数枚举最终 $m$ 道题的答案。

具体的，比如 $m=3$，我们知道最终三道题有可能：

• 全对、全错。由于我们知道前面 $n-3$ 道题中答案为 Y 的数量，以及所有题目中答案为 Y 的数量 $t$，因此这种情况 $1$ 次输出即可。

• $2$ 对 $1$ 错、$2$ 错 $1$ 对，则我们可以枚举那个唯一的一道对/错题，最多需要 $m$ 次。

综上所述，每 $4$ 道题目最多需要 $3$ 次猜测，如果 $n$ 能被 $4$ 整除，加上第一次全猜对，共需要 $0.75 \times n + 1$ 次。

如果 $n$ 不能被 $4$ 整除，假设余数为 $m(0 \leq m \leq 3)$，那么剩下来的 $m$ 道题目最多需要 $m$ 次猜测，因此总的猜测次数最多需要 $\lfloor 0.75 \times n + 1 + m \rfloor \le \lfloor 0.75 \times n + 4 \rfloor$。因此猜测次数放到 $\min(n+2, \ \lfloor0.75 \times n + 4 \rfloor)$ 是没有问题的。

然后我们就可以愉快地写出代码了：

出题人代码：

#include<bits/stdc++.h>
#define check(cnt) if(cnt==n) {return 0;}
using namespace std;
char a[10009];
char b[10009];
int cnt1,cnt2;
int n,k,t;
int now=1;
double kk;
void print(){
	for(int i=1;i<=n;i++) printf("%c",b[i]);
	printf("\n");
	cout.flush();
}
void prin(){
	for(int i=1;i<=n;i++) printf("%c",a[i]);
	printf("\n");
	cout.flush();
}
int ft(){
	int cnt=0;
	for(int i=1;i<=now-1;i++){
		if(b[i]=='Y') cnt++;
	}
	return cnt;
}
void doit(){
	for(int i=1;i<=n;i++) a[i]='Y';
}
int main(){
	scanf("%d",&n);
	scanf("%f",&kk);
	for(int i=1;i<=n;i++) b[i]=a[i]='Y';
	prin();
	scanf("%d",&t);
	check(t);
	while(now<=n-3){
		doit();
		a[now]=a[now+1]='N';
		prin();
		scanf("%d",&cnt1);
		check(cnt1);
		if(cnt1==t-2||cnt1==t+2){
			if(cnt1==t-2) b[now]=b[now+1]='Y';
			else b[now]=b[now+1]='N';
			now+=2;
			if(now==n+1) break;
			if(now>n){
				now-=2;
				break;
			}
			continue;
		}
		a[now]='Y',a[now+1]=a[now+2]=a[now+3]='N';
		prin();
		scanf("%d",&cnt1);
		check(cnt1);
		
		a[now]=a[now+2]='N',a[now+1]=a[now+3]='Y';
		prin();
		scanf("%d",&cnt2);
		check(cnt2);
		
		if(cnt1==t-3){
			b[now]='N',b[now+1]=b[now+2]=b[now+3]='Y';
		}
		else if(cnt1==t-1){
			if(cnt2==t-2) b[now]=b[now+2]=b[now+3]='Y',b[now+1]='N';
			if(cnt2==t) b[now]=b[now+3]='N',b[now+1]=b[now+2]='Y';
			if(cnt2==t+2) b[now]=b[now+2]='N',b[now+1]=b[now+3]='Y';
		}
		else if(cnt1==t+1){
			if(cnt2==t-2) b[now]=b[now+2]='Y',b[now+1]=b[now+3]='N';
			if(cnt2==t) b[now]=b[now+3]='Y',b[now+1]=b[now+2]='N';
			if(cnt2==t+2) b[now]=b[now+2]=b[now+3]='N',b[now+1]='Y';
		}
		else if(cnt1==t+3){
			b[now]='Y',b[now+1]=b[now+2]=b[now+3]='N';
		}
		now+=4;
		if(now==n+1) break;
		if(now>n){
			now-=4;
			break;
		}
	}
	int rest=n-now+1,k=ft();
	
	if(rest==1){
		if(k==t) b[n]='N';
		else b[n]='Y';
	}
	else if(rest==2){
		if(k==t){
			b[n-1]=b[n]='N';
		}
		else if(k==t-2){
			b[n-1]=b[n]='Y';
		}
		else{
			b[n-1]='Y',b[n]='N';
			print();
			scanf("%d",&cnt1);
			check(cnt1);
			
			b[n-1]='N',b[n]='Y';
			print();
			scanf("%d",&cnt1);
			check(cnt1);
		}
	}
	else if(rest==3){
		if(k==t){
			b[n-2]=b[n-1]=b[n]='N';
		}
		else if(k==t-3){
			b[n-2]=b[n-1]=b[n]='Y';
		}
		else if(k==t-1){
			b[n-2]=b[n-1]=b[n]='N';
			b[n-2]='Y',print();
			scanf("%d",&cnt1);
			check(cnt1);
			
			b[n-2]=b[n-1]=b[n]='N';
			b[n-1]='Y',print();
			scanf("%d",&cnt1);
			check(cnt1);
			
			b[n-2]=b[n-1]=b[n]='N';
			b[n]='Y',print();
			scanf("%d",&cnt1);
			check(cnt1);
		}
		else if(k==t-2){
			b[n-2]=b[n-1]=b[n]='Y';
			b[n-2]='N',print();
			scanf("%d",&cnt1);
			check(cnt1);
			
			b[n-2]=b[n-1]=b[n]='Y';
			b[n-1]='N',print();
			scanf("%d",&cnt1);
			check(cnt1);
			
			b[n-2]=b[n-1]=b[n]='Y';
			b[n]='N',print();
			scanf("%d",&cnt1);
			check(cnt1);
		}
	}
	print();
	scanf("%d",&cnt1);
	return 0;
}

验题人代码：

#include <bits/stdc++.h>

using namespace std;

int n;
double k;
string answer;

void setAnswer(int start, int end, string guess)
{
    for (int i = start; i <= end; i++)
        answer[i] = guess[i - start];
}

void printGuess(int start, int end, string guess)
{
    for (int i = 0; i < n; i++)
    {
        if (i >= start && i <= end) cout << guess[i - start];
        else cout << 'Y';
    }
    cout << endl;
}

int main(int argc, char *argv[])
{
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);

    cin >> n >> k;
    int cntOfGuess = min(n+2, (int)(k * n + 4));
    
    int a;
    for (int i = 0; i < n; i++) answer += 'Y';
    cout << answer << endl;
    cin >> a;
    
    int idx = 0, cnt1, cnt2;
    while (cntOfGuess--)
    {
        if (idx + 1 == n || idx + 3 == n)
        {
            printGuess(idx, idx, "N");
            cin >> cnt1;
            if (cnt1 == a - 1) setAnswer(idx, idx, "Y");
            else setAnswer(idx, idx, "N");
            idx += 1;
        }
        else
        {
            printGuess(idx, idx + 1, "NN");
            cin >> cnt1;
            if (cnt1 == a - 2) { setAnswer(idx, idx + 1, "YY"); idx += 2; }
            else if (cnt1 == a + 2) { setAnswer(idx, idx + 1, "NN"); idx += 2; }
            else if (idx + 3 < n)
            {
                printGuess(idx, idx + 3, "YNNN");
                cin >> cnt1;
                printGuess(idx, idx + 3, "NYNY");
                cin >> cnt2;
                if (cnt1 == a - 3 && cnt2 == a) setAnswer(idx, idx + 3, "NYYY");
                if (cnt1 == a - 1 && cnt2 == a - 2) setAnswer(idx, idx + 3, "YNYY");
                if (cnt1 == a - 1 && cnt2 == a) setAnswer(idx, idx + 3, "NYYN");
                if (cnt1 == a - 1 && cnt2 == a + 2) setAnswer(idx, idx + 3, "NYNY");
                if (cnt1 == a + 1 && cnt2 == a - 2) setAnswer(idx, idx + 3, "YNYN");
                if (cnt1 == a + 1 && cnt2 == a) setAnswer(idx, idx + 3, "YNNY");
                if (cnt1 == a + 1 && cnt2 == a + 2) setAnswer(idx, idx + 3, "NYNN");
                if (cnt1 == a + 3 && cnt2 == a) setAnswer(idx, idx + 3, "YNNN");
                idx += 4;
            }
            else
            {
                printGuess(idx, idx + 1, "YN");
                cin >> cnt1;
                if (cnt1 == a + 1) setAnswer(idx, idx + 1, "YN");
                else setAnswer(idx, idx + 1, "NY");
                idx += 2;
            }
        }
        if (idx >= n) { cout << answer << endl; break; }
    }

    return 0;
}

两份代码核心思想相同，但实现方式略有不同。需者自取。