题解 CF1137D 【Cooperative Game】

mrsrz · 2019-03-11 13:10:18 · 题解

用Floyd判圈法。即一个人每走一步，则另一个人走两步。由于有环，所以在某一时刻，跑得快的一定会追上跑得慢的，且此时跑的慢的一定没跑满一圈。

假设跑得慢的走了t+k步，那么跑得快的走了2t+2k步（0\leqslant k < c）。

忽略在链上的t步，由于它们现在在同一个点，所以k\equiv t+2k\pmod c。

转化得t+k\equiv 0\pmod c，t\equiv c-k\pmod c。

当前这两个人所处的位置再走c-k步恰好是目标位置，而由于t和c-k模c同余，所以再走t步就能到目标位置。

由于其他在起点的人走t步后也能到目标位置，所以我们无需知道t和c的具体位置，只需要让他们继续走，相遇的时候就是在目标位置。

一共花费的步数为3t+2k< 3t+3c。

Code：

#include<cstdio>
int group[11],step1=1,step2=2;
inline void update(){
    int x;
    static char s[12];
    fflush(stdout),scanf("%d",&x);
    for(int i=1;i<=x;++i){
        scanf("%s",s);
        for(int j=0;s[j];++j)group[s[j]^'0']=i;
    }
}
int main(){
    puts("next 0"),update();
    puts("next 0 1"),update();
    for(int t=1;;++t){
        if(t&1)puts("next 0 1"),++step1,++step2;else puts("next 0"),++step2;
        update();
        if(group[0]==group[1])break;
    }
    while(group[0]!=group[2])
    puts("next 0 1 2 3 4 5 6 7 8 9"),update();
    puts("done"),fflush(stdout);
    return 0;
}