【CF1137D】Cooperative Game 题解

题目大意

  这是一道交互题。
  有这样一个 $\rho$ 型的有向图：

  但是 $t$ 和 $c$ 都是未知的。
  你有 10 个棋子一开始在起点（标了房子那个），你要把他们都走到终点（标了棋子的那个）。每一步，你可以任意指定一些棋子，让这些棋子都向前走一步。然后电脑会告诉你，哪些棋子是在同一个格子里的。当你认为你把所有棋子都放到终点了的时候，就可以 end 了。
  你的步数不能超过 $3(t+c)$。
  $t+c \leq 1000$

题解

  这肯定是要用 Floyd 判圈了，有意思的是判完圈之后的小分析，这个分析有点妙。

  一开始，一个人一次走两步，另一个人一次走一步，那么他们必在环中相遇。
  并且慢者在环上最多走一圈。因为如果慢者走了多于一圈，那么快者一定走了两圈了，因此就一定会超过他，不可能跟在他屁股后面转。

  设他们相遇的地点离终点距离为 $x$，则慢者的路程为 $t+x$，快者的路程为 $t+kc+x$，$k$ 是快者走过的圈数。
  由快者速度是慢者两倍可得 $2(t+x)=t+kc+x$，即 $t+x=kc$，即 $t+x \equiv 0 \pmod{c}$

  也就是说，他们相遇后再走 $t$ 步就到终点了。
  而剩下的在起点的 8 个人也是走 $t$ 步到终点！！！
  所以大家一起走，直到相遇，就行了。

  第一个过程的步数，即为快者的步数，不超过 $2(t+c)$，第二个过程的步数恰好为 $t$，所以总步数在 $3(t+c)$ 范围内。