GMOJ 3983.乾坤大挪移
Solution
首先 X, Y 的正负性是没有影响的。
分三种情况讨论:
1.无解:
有解的充要条件是 X, Y 奇偶性相同
-
X, Y 同为偶数:
有两种走法:- X, Y 分别用 (2) 走到 (0, 0)
- X, Y 先走 (1) 再走 (2)
答案就是两种走法所需步数的最小值。
为什么会有走法2呢?
考虑走法1中 x, y 一直走 2(L - 1) 步,直到不能走 (x < 2L, y < 2L),
如果此时 x < L, y < L 且 x != y 的话,那么需要两步,但是我们却可以通过调整走法1
中最后一步的大小使得 x = y ,那么就只需要再走1步 (2) 就可以了。
那么我们把这最后一步 (2) 放到开始,并且贪心地让它最大。
注意:过程中要时刻保证 X, Y 为偶数。
-
X, Y 同为奇数:
先通过 (1) 使 X, Y 变成偶数,然后按照偶数地走法就好了
最后就是高精度操作操作了 (代码打得好丑)
(以上纯属个人理解出锅不背)
CODE
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 500
#define L 10
#define fo(i, x, y) for(int i = x; i <= y; i ++)
#define fd(i, x, y) for(int i = x; i >= y; i --)
#define re return
#define Max(x, y) (x > y ? x : y)
struct Num {
int x[N + 1], tot;
void Read() {
char ch = getchar(); tot = 0;
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') x[ ++ tot ] = ch - 48, ch = getchar();
fo(i, 1, (tot >> 1)) swap(x[i], x[tot - i + 1]);
}
bool operator > (const Num &u) {
if (tot != u.tot) re tot > u.tot;
fd(i, tot, 1) if (x[i] != u.x[i])
re x[i] > u.x[i];
re 0;
}
void operator -= (const Num u) {
fd(i, u.tot, 1) x[i] -= u.x[i];
fo(i, 1, tot) if (x[i] < 0)
x[i] += 10, -- x[i + 1];
while (tot && ! x[tot]) -- tot;
}
void Init() { fo(i, 1, tot) x[i] = 0; tot = 0; }
bool operator != (const Num &u) {
if (tot != u.tot) re 1;
fo(i, 1, tot) if (x[i] != u.x[i])
re 1;
re 0;
}
void Updata() {
fo(i, 1, N) if (x[i] >= L)
x[i + 1] += x[i] / L, x[i] %= L;
tot = N;
while (tot && ! x[tot]) -- tot;
}
void operator += (const Num &u) {
tot = Max(tot, u.tot);
fo(i, 1, tot) x[i] += u.x[i];
Updata();
}
} a, b, c, c1, d, ans;
bool Cmp(Num &u, int l, Num &v) {
if (u.tot - l + 1 > v.tot) re 1;
fd(i, v.tot, 1) if (u.x[l + i - 1] != v.x[i])
re u.x[l + i - 1] > v.x[i];
re 1;
}
void Del(Num &u, int l, Num &v) {
fd(i, v.tot, 1) u.x[l + i - 1] -= v.x[i];
fo(i, l, u.tot) if (u.x[i] < 0)
u.x[i] += 10, -- u.x[i + 1];
while (u.tot && ! u.x[u.tot]) -- u.tot;
}
Num C(Num &u, Num &v) {
d.Init();
fd(i, u.tot - v.tot + 1, 1) {
while (Cmp(u, i, v)) {
Del(u, i, v);
++ d.x[i];
}
}
d.Updata();
return d;
}
Num a1, a2, a3;
Num Get_ans(Num u, Num v) {
a3 = C(u, c1); a3 += C(v, c1);
if (u.tot) ++ a3.x[1];
if (v.tot) ++ a3.x[1];
a3.Updata();
return a3;
}
Num Get(Num u, Num v) {
a1 = Get_ans(u, v);
u > c ? (u -= c, v -= c) : (v -= u, u -= u);
if (u.x[1] & 1) {
++ u.x[1], ++ v.x[1];
u.Updata(), v.Updata();
}
a2 = Get_ans(u, v);
++ a2.x[1]; a2.Updata();
return a1 > a2 ? a2 : a1;
}
int main() {
freopen("move.in", "r", stdin);
freopen("move.out", "w", stdout);
int T; scanf("%d", &T);
while (T --) {
fo(i, 1, N) a.x[i] = b.x[i] = c.x[i] = c1.x[i] = 0;
a.Read(), b.Read(), c.Read();
a.Updata(), b.Updata();
if ((a.x[1] & 1) ^ (b.x[1] & 1)) {
puts("Poor MLG!"); continue;
}
-- c.x[1];
fo(i, 1, c.tot) if (c.x[i] < 0)
c.x[i] += L, -- c.x[i + 1];
while (! c.x[c.tot]) -- c.tot;
fo(i, 1, c.tot) c1.x[i] = (c.x[i] << 1);
c1.Updata();
if (a > b) swap(a, b);
if (a.x[1] & 1) {
a > c ? (a -= c, b -= c) : (b -= a, a -= a);
if (a.x[1] & 1) {
++ a.x[1], ++ b.x[1];
a.Updata(), b.Updata();
}
ans = Get(a, b);
++ ans.x[1];
ans.Updata();
} else
ans = Get(a, b);
fd(i, ans.tot, 1) printf("%d", ans.x[i]);
puts("");
}
return 0;
}