题解：CF1137D Cooperative Game

PDAST · 2024-12-25 14:00:54 · 题解

思路

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

证明

我们设走的慢的棋子在环路上走了 x 步，则它一共走了 T+x 步，另一个棋子走了 2(T+x) 步，而我们知道，快的棋子一定比慢的多走了 C 的整数倍，所以 2(T+x)-(T+x) 即 T+x 必定是 C 的整数倍。而此时，留在起点的棋子相距终点 T 步，在环上的两个棋子再走 T+x-x 步就能到达终点，所以可以让全部棋子一起向前走 T 步以达到目的。

代码

#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;
}