https://codeforces.com/contest/1138/problem/F

题意

有一条长为t的链,一个长为c的环,定义终点为链和环相连环上的第一个点,现在有10个人在起点,你每次可以选择一部分人向前移动一步,然后会返回十个人的分组情况(在同一个点的为一组),一旦进入了环里就只会在环里转圈,让你在最多\(3*(t+c)\)次操作下,让所有人走到终点

题解

• 最多只能\(3*(t+c)\)次操作,但是现在t和c都不知道,所以无法用随机法
• 用两个人a,b,a每次走一步,b每次走两步,当两人第一次到相遇时有\(t+k=c\)
• 在换过来有\(t=c-k\),意味着两人第一次相遇后所有人都向前走,最终全部人会相遇在某一点且这一点就是终点

代码

#include<bits/stdc++.h>

using namespace std;

int read(){

	int n;string s;

	cin>>n;

	for(int i=0;i<n;i++)cin>>s;

	return n;

}

int main(){

	cout<<"next 0 1"<<endl;

	cout.flush();

	read();

	cout<<"next 1"<<endl;

	cout.flush();

	while(read()==3){

		cout<<"next 0 1"<<endl;

		cout.flush();

		read();

		cout<<"next 1"<<endl;

		cout.flush();

	}

	cout<<"next";

	for(int i=0;i<10;i++)cout<<" "<<i;cout<<endl;

	cout.flush();

	while(read()==2){

		cout<<"next";

		for(int i=0;i<10;i++)cout<<" "<<i;cout<<endl;

		cout.flush();

	}

	cout<<"done"<<endl;

	cout.flush();

}