题解：CF1137D Cooperative Game

思路

想到可以让一个棋子走的更快，在环路上从后面追上另一个，一旦相遇，便停止。此时再让所有棋子向前走

T

步便可以达到目的。

证明

我们设走的慢的棋子在环路上走了

x

步，则它一共走了

T+x

步，另一个棋子走了

2(T+x)

步，而我们知道，快的棋子一定比慢的多走了

C

的整数倍，所以

2(T+x)-(T+x)

即

T+x

必定是

C

的整数倍。而此时，留在起点的棋子相距终点

T

步，在环上的两个棋子再走

T+x-x

步就能到达终点，所以可以让全部棋子一起向前走

T

步以达到目的。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
string st[21];
bool get(int p){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>st[i];
	return n!=p;
}
signed main(){
	int t=0;
	while(1){
		t++;
		cout<<"next 0"<<endl;
		get(2);
		cout<<"next 0 1"<<endl;
		if(!get(2))break;
	}
	while(1){
		cout<<"next ";
		for(int i=0;i<10;i++)cout<<i<<" ";
		cout<<endl;
		if(!get(1))break;
	}
	cout<<"done"<<endl;
}

题解：CF1137D Cooperative Game

文章操作

思路

证明

代码

相关推荐

评论

题解：CF1137D Cooperative Game