题目大意:
三个棋子在 \(a,b,c\) 位置,通过题目给出的跳动规则,问能否跳到 \(x,y,z\),如果能,最少多少步?
正文:
假设三个棋子分别在 \(a,b,c\quad(a<b<c)\),跳动规则其实就三个:
-
\(b\) 向 \(a\) 跳。
-
\(b\) 向 \(c\) 跳。
-
\(a,c\) 里 \(b\) 近的向内跳。
而第 1,2 个规则都会扩大范围,只有第 3 个规则会缩小范围,@ButterflyDew (uid=63727) 在题解中提到 对缩小边界的跳法具有唯一性,也就是说将初始位置和终点位置都用第 3 规则跳,若最后产生交集(即相等)说明能够到达。
把三个数看作一个三元数 \((a,b,c)\) 作为一棵树的一个节点的状态,也就是说问题就是树上两个不同节点的距离,像 LCA 一样,先让两个节点跳到一个相同的深度,再二分距离,让这两个节点同时向上跳,最后就能出答案。
代码:
int jump(int a, int b, int c)
{
int d1 = b - a, d2 = c - b, cnt = 0;
if (d1 < d2)
{
int d = d2 % d1;
cnt = d2 / d1;
if (!d)
{
cnt --;
d += d1;
}
cnt += jump (c - d - d1, c - d, c);
} else
if (d1 > d2)
{
int d = d1 % d2;
cnt = d1 / d2;
if (!d)
{
cnt --;
d += d2;
}
cnt += jump (a, a + d, a + d + d2);
} else
arr[0] = a, arr[1] = b, arr[2] = c;
return cnt;
}
void go(int a, int b, int c, int step)
{
if(!step)
{
arr[0] = a, arr[1] = b, arr[2] = c;
return;
}
int d1 = b - a, d2 = c - b, cnt = 0;
if (d1 < d2)
{
int d = d2 % d1;
cnt = d2 / d1;
if (!d)
{
cnt --;
d += d1;
}
if(step >= cnt)
go (c - d - d1, c - d, c, step - cnt);
else
go (c - d - d1 * (cnt - step + 1), c - d - d1 * (cnt - step), c, 0);
} else
if (d1 > d2)
{
int d = d1 % d2;
cnt = d1 / d2;
if (!d)
{
cnt --;
d += d2;
}
if(step >= cnt)
go (a, a + d, a + d + d2, step - cnt);
else
go (a, a + d + d2 * (cnt - step), a + d + d2 * (cnt - step + 1), 0);
} else
arr[0] = a, arr[1] = b, arr[2] = c;
}
bool check(int mid)
{
go(beg[0], beg[1], beg[2], mid);
arr1[0] = arr[0], arr1[1] = arr[1], arr1[2] = arr[2];
go(end[0], end[1], end[2], mid);
if (arr1[0] != arr[0] && arr1[1] != arr[1] && arr1[2] != arr[2])
return 0;
return 1;
}
int main()
{
scanf ("%d%d%d%d%d%d", &beg[0], &beg[1], &beg[2], &end[0], &end[1], &end[2]); sort (beg, beg + 3);sort (end, end + 3);
int step1 = jump(beg[0], beg[1], beg[2]);
arr1[0] = arr[0], arr1[1] = arr[1], arr1[2] = arr[2];
int step2 = jump(end[0], end[1], end[2]);
if (arr1[0] != arr[0] && arr1[1] != arr[1] && arr1[2] != arr[2])
{
puts("NO");
return 0;
}
if (step1 < step2)
{
ans = step2 - step1;
go(end[0], end[1], end[2], step2 - step1);
end[0] = arr[0], end[1] = arr[1], end[2] = arr[2];
}
if (step1 > step2)
{
ans = step1 - step2;
go(beg[0], beg[1], beg[2], step1 - step2);
beg[0] = arr[0], beg[1] = arr[1], beg[2] = arr[2];
}
int l, r = min(step1, step2);
while (l < r)
{
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
printf("YES\n%d\n", (l * 2 + ans));
return 0;
}