题解 CF1137D 【Cooperative Game】

· · 题解

BLOG

[Codeforces1137D]Cooperative Game

Tags：题解

题意

这是一道交互题。

给你一张下面这样的地图，由一条长为t的有向链和一个长为c的环构成。 现在你有10颗棋子，编号0到9，你不知道t和c的值，你每次可以移动若干颗棋子。

请你输出方案，使得所有棋子走到环和链的交点处，并在走到时输出done。

你每次可以输出next a b c ...，交互库将返回k a1 a2 ... ak表示当前有k个位置有棋子，ai表示一个字符串，表示第i个位置的棋子编号是什么。

你的移动次数不能超过3(t+c)，t+c\le 1000。

题解

神仙题，一直在想10颗棋子的二进制意义，然而t和c再大也没有关系。

步骤：

选定两颗棋子0,1，0每次都移动，1每两次移动一次。

走了2t步之后1刚好到达交点T，把环按照以T为1按边的方向依次编号，则此时0在环上的t位置。

这时0还需要c-t步追上（到） 1，追上的位置是c-t。

然后惊奇地发现：把所有点同时走t步就可以让所有点都在T上了！

服了服了。这场掉分掉得爽啊（第一次掉分）

代码

#include<iostream>
using namespace std;
char s[100];
int In() {int x,p;scanf("%d",&x);for(p=x;p;p--) scanf("%s",s);return x;}
int main()
{
    while(1)
    {
        puts("next 0");fflush(stdout);In();
        puts("next 0 1");fflush(stdout);
        if(In()==2) break;
    }
    while(1)
    {
        puts("next 0 1 2 3 4 5 6 7 8 9");
        fflush(stdout);if(In()==1) break;
    }
    puts("done");fflush(stdout);
}