本做法利用随机化，给出了 $\bf S=20$ 的策略，并且只需要往程序里内置 $5$ 个数的打表。更大的打表可以做到 $\bf19$ 次。最喜欢交互的一集。

人类看到这个题，可能会有一些正紧想法，然后可能有若干提升随机化成功率的做法，但是发现好像都不如纯随机。

对于一个目前可能成为答案的集合 $S$，一次询问会把 $S$ 划分成 $T_1,\cdots ,T_k$，我直接取 $\max(|T_i|)$ 最小的作为当前的最优询问。

关于为什么想到随机：这个问题蕴含了很多信息，但是好像很难利用好（难以刻画成一个区间或者优美的性质），于是考虑用 Wordle 的思路来解这道题。然后大胆写了一个随机化发现效果极好。

由于 $m=3000$ 较小，且有 $10$ 秒，我们可以在预处理时尝试若干询问并取最优的。我在代码中的实现方式为先随机若干个序列取出最优的，然后对其做爬山。

手动尝试第 $i$ 次询问集合大小的要求，可以做到 $20$ 次。把代码中随机的次数调大可以在几分钟内得出 $19$ 次的做法。

::::info[代码中的注意点]

• $80$ 行爬山一定是 $\le$，而不是 $<$，让程序可以做更多尝试，而不是局部最优解过早收敛，可能优化了 $7$ 次

• 生成时让偶数生成的概率大一点，优化了 $1$ 次

• 优化其余部分的效率，增加爬山运行次数 ::::

::::info[其他可能的优化]

• 爬山换成退火或者其他算法

• 更合理的生成随机数概率分布

• 对于不同阶段的询问使用不同的随机策略（尤其最后一次）

• 把取最大的换成信息熵或者其他评分方式

• 使用长时间的预处理 ::::

$S=20$ 代码：

#include "pudding.h"
#include<bits/stdc++.h>
#define query query_tastiness
#define pb push_back
#define popcnt __builtin_popcountll
#define debug printf("Passed line %d\n", __LINE__)

using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> PII;

int query(vint x);

template<typename T> inline void checkmax(T &x, const T &y){if (x<y) x = y;}

template<typename T> inline void checkmin(T &x, const T &y){if (x>y) x = y;}

const int N = 3500, K = 1e4;
int val[N], topd, Test[30];
int g[N+1][N+1];
int sz[5] = {0, 5, 5, 5, 5}, mx[5];
vint v[K];

struct Data{

	vint ask;
	map<int, int> mp;

}e[K];

inline int Rand(){
	int x = rand()%N+1;
	if (x%2) x = rand()%N+1;
	return x;
}

inline int f(vint x){
	sort(x.begin(), x.end()); int ans = 0;
	for (int i = 0;i+1<x.size();i++) ans += g[x[i]][x[i+1]];
	return ans;
}

inline int cal(vint &x, vint &test){
	int ans = 0, p, t, top = 0, topt = 0, pos = 0;
	for (int i: test) Test[++topt] = i;
	Test[topt+1] = 0;
	sort(Test+1, Test+topt+1);
	pos = 1;
	for (int i: x){
		while (pos<=topt && Test[pos]<i) pos++;
		val[++top] = -g[Test[pos]][Test[pos-1]] + g[Test[pos]][i] + g[Test[pos-1]][i];
	}
	sort(val+1, val+top+1);
	p = 1;
	while (p<=top){
		t = p;
		while (t<top && val[t+1] == val[p]) t++;
		checkmax(ans, t-p+1);
		p = t+1;
	}
	return ans;
}

inline void solve(int id, vint all, int sz, int lst){
	vint vec, ans; int mn = 1e8, Now, p, x;
	
	if (all.size()<=sz+1){
		ans = all, mn = 1;
		if (ans.size()>1) ans.erase(ans.begin());
	}
	else if (all.size() == 3000) ans = {700, 1980, 150, 1260, 2610};
	else{
		for (int i = 1;i<=30000;i++){
			vec.clear();
			for (int j = 1;j<=sz;j++) vec.pb(Rand());
			Now = cal(all, vec);
			if (Now<mn) mn = Now, ans = vec;
		}

		for (int i = 1;i<=90000;i++){
			p = rand()%sz, x = ans[p];
			ans[p] = Rand();
			Now = cal(all, ans);
			if (Now<=mn){ // <=
				mn = Now;
			}
			else ans[p] = x;
		}
	}

	e[id].ask = ans;
	if (lst){
		for (int i: all){
			ans.pb(i);
			e[id].mp[f(ans)] = i;
			ans.pop_back();
		}
	}
	else{
		for (int i: all){
			ans.pb(i), p = f(ans), ans.pop_back();
			if (!e[id].mp.count(p)) e[id].mp[p] = ++topd;
			v[e[id].mp[p]].pb(i);
		}
	}
}

void dfs(int step, int id){
	checkmax(mx[step], (int)v[id].size());
	if (step == 4){
		solve(id, v[id], sz[step], 1);
		return;
	}
	int l = topd+1, r;
	solve(id, v[id], sz[step], 0);
	r = topd;
	for (int i = l;i<=r;i++) dfs(step+1, i);
}

void init(int c, int t){
	srand(0);
	for (int i = 1;i<=N;i++){
		for (int j = i;j<=N;j += i){
			for (int k = i;k<=N;k += i) g[j][k] = i;
		}
	}
	for (int i = 1;i<=3000;i++) v[1].pb(i);
	topd = 1;
	dfs(1, 1);
    return;
}

int find_tastiness(int c, int m){
	int p = 1;
	for (int i = 1;i<=4;i++){
		p = e[p].mp[query(e[p].ask)];
	}
	return p;
}