Description
跳跳棋是在一条数轴上进行的. 棋子只能摆在整点上. 每个点不能摆超过一个棋子. 我们用跳跳棋来做一个简单的游戏: 棋盘上有 \(3\) 颗棋子, 分别在 \(a, b, c\) 这三个位置. 我们 要通过最少的跳动把他们的位置移动成 \(x, y, z\). (棋子是没有区别的) 跳动的规则很 简单, 任意选一颗棋子, 对一颗中轴棋子跳动. 跳动后两颗棋子距离不变. 一次只允许跳过 \(1\) 颗棋子.
写一个程序, 首先判断是否可以完成任务. 如果可以, 输出最少需要的跳动次数.
Input
第一行包含三个互不相同的整数 \(a, b, c\), 表示当前棋子的位置;
第二行包含三个互不相同的整数 \(x, y, z\), 表示目标位置.
Output
如果无解, 输出一行 NO
. 如果可以到达, 第一行输出 YES
, 第二行输出最少步数.
Sample Input
1 2 3
0 3 5
Sample Output
YES
2
Data Range
对于 20% 的数据, 满足: 0|a|,|b|,|c|,|x|,|y|,|z|10 $
对于 40% 的数据, 满足: 0|a|,|b|,|c|,|x|,|y|,|z|10000 $
对于 100% 的数据, 满足: 0|a|,|b|,|c|,|x|,|y|,|z|10^9 $
Explanation
首先 20 分的暴力是给暴搜的多么良心......
然后我们发现这样一件事: 就是说我们可以把三个棋子的状态用一个三元组 \((a, b, c)\) 来表示. 对应地, 由于一个棋子不能跳过两个棋子, 固然只可能两两对换. 然后一种状态 \((a, b, c)\) 的接下来两个状态一定是 \((2a-b, b, c)\) 或者 \((a, b, 2b-c)\) 之中的一个. 这样所有状态就构成了一个树形结构, 可以直接在上面查询最近公共祖先, 即得结果.
再考虑优化这个问题的情况. 首先树上节点过多, 不可能在 \(O(n)\) 时间内完成. 我们考虑 这棵树不一定需要构造出来, 而且在三个点之中只有两个点十分接近的时候, 贪心地, 两者 会不停对称反转接近终点位置. 这样我们就可以用类似倍增 LCA 的方法, 遂得解.
刚才这个算法的时间复杂度是 \(O(\log n)\) 的.
Source Code
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
#define range(_begin,_end) rep(_,_begin,_end)
using namespace std;
typedef long long lli;
const int maxn = 5;
const int infinit = 1000000000;
int a[maxn], b[maxn];
struct tup { int a[maxn]; };
bool operator != (tup a, tup b) {
range(1, 3) if (a.a[_] != b.a[_]) return true;
return false; }
typedef pair<tup,int> prti;
tup calc_dfs(int a[], int k, int& depth)
{
tup res;
int t1 = a[2] - a[1], t2 = a[3] - a[2];
range(1, 3) res.a[_] = a[_];
if (t1 == t2) {
return res;
} else if (t1 < t2) {
int t = min(k, (t2 - 1) / t1);
k -= t; depth += t;
res.a[1] += t * t1;
res.a[2] += t * t1;
} else { // if (t1 > t2)
int t = min(k, (t1 - 1) / t2);
k -= t; depth += t;
res.a[2] -= t * t2;
res.a[3] -= t * t2;
}
// Inversal?
if (k) return calc_dfs(res.a, k, depth);
return res;
}
pair<tup, int> calc(int a[], int k)
{
int depth = 0;
tup res = calc_dfs(a, k, depth);
return make_pair(res, depth);
}
tup calc_s(int a[], int k)
{
int depth = 0;
return calc_dfs(a, k, depth);
}
int main(int argc, char** argv)
{
// Read in the coordinates and sort
scanf("%d%d%d", &a[1], &a[2], &a[3]);
scanf("%d%d%d", &b[1], &b[2], &b[3]);
sort(a + 1, a + 4);
sort(b + 1, b + 4);
// Building (imaginary) tree
prti pr1 = calc(a, infinit),
pr2 = calc(b, infinit);
tup t1 = pr1.first, t2 = pr2.first;
int d1 = pr1.second, d2 = pr2.second;
// The root, respectively are t1 and t2 for a, b
// Which has the depth of d1 and d2
if (t1 != t2) {
printf("NO\n");
return 0;
} else if (d1 > d2) {
swap(d1, d2); swap(t1, t2);
range(1, 3) swap(a[_], b[_]);
}
// Minor modifications
int res = d2 - d1;
t1 = calc_s(b, res);
range(1, 3) b[_] = t1.a[_];
// Binary searching
int l = 0, r = d1;
while (l <= r) {
int mid = (l + r) / 2;
if (calc_s(a, mid) != calc_s(b, mid))
l = mid + 1;
else
r = mid - 1;
}
res += 2 * l;
printf("YES\n%d\n", res);
return 0;
}