思路
要求步数最少的操作方案，先考虑操作 \(n\) 步能走到 \((x,y)\) 的条件：
- \(\frac{n(n + 1)}{2} \geq |x| + |y|\)。显然成立，走到 \((x,y)\) 至少需要走过 \(|x| + |y|\) 个单位长度。
- \(\frac{n(n + 1)}{2} \equiv |x| + |y| \pmod 2\)。因为对于第 \(i\) 步会使当前位置的横坐标或纵坐标加 \(i\) 或减 \(i\)，对于横坐标和纵坐标在模 \(2\) 意义下的影响，无论是 \(+i\) 还是 \(-i\) 均为 \(i \mod 2\)。最后在 \(n\) 步过后能走到 \((x,y)\) 那么 \(n\) 步过后能走到一个 \((x',y')\) 满足 \(x' \equiv x \pmod 2,y' \equiv y \pmod 2\) 的点显然是原命题的一个必要条件。
不妨猜测上面两个必要条件加起来是充要的，考虑归纳法证明：
- 当 \(n = 1\) 时，可能走到的点只有 \((0,1),(0,-1),(1,0),(-1,0)\)，这些点均满足条件。
- 当 \(n = 2\) 时，可能走到的点只有 \((1,0),(2,1),(2,-1),(3,0)\)，这些点也均满足条件。
- 当 \(n > 2\) 时，假定 \(n' = n - 1\) 时成立，为了方便叙述，这里假设 \(x \geq |y|\) 其余情况证明方式同理。不妨用这一步操作将 \((x,y)\) 走到 \((x - n,y)\)。若 \(x \geq n\)，那么有 \(\frac{n(n + 1)}{2} - n \geq |x| + |y| - n\) 以及 \(\frac{n(n + 1)}{2} - n \equiv x - n + |y| \pmod 2\)；若 \(x < n\)，那么有 \(n - x + |y| \leq n \leq \frac{n(n + 1)}{2} - n\) 以及 \(\frac{n(n + 1)}{2} - n \equiv n - x + |y| \pmod 2\)。
Q.E.D.
证出充要性只需要照着证明过程，从 \((x,y)\) 倒着走回 \((0,0)\) 就行了。
Code
#include <bits/stdc++.h>
#define re register
#define int long longusing namespace std;int x,y;
const int dx[] = {-1,1,0,0};
const int dy[] = {0,0,-1,1};
const char ch[] = {'E','W','N','S'};inline int read(){int r = 0,w = 1;char c = getchar();while (c < '0' || c > '9'){if (c == '-') w = -1;c = getchar();}while (c >= '0' && c <= '9'){r = (r << 3) + (r << 1) + (c ^ 48);c = getchar();}return r * w;
}inline bool check(int n,int x,int y){int sum = (n + 1) * n / 2;return (sum >= abs(x) + abs(y) && sum % 2 == (abs(x) + abs(y)) % 2);
}inline void solve(int tid){int n = 0;vector<char> ans;x = read(),y = read();while (!check(n,x,y)) n++;for (re int i = n;i;i--){for (re int w = 0;w < 4;w++){int tx = x + dx[w] * i,ty = y + dy[w] * i;if (check(i - 1,tx,ty)){x = tx,y = ty;ans.push_back(ch[w]);break;}}} reverse(ans.begin(),ans.end());printf("Case #%lld: ",tid);for (char c:ans) putchar(c);puts("");
}signed main(){int T = read();for (re int i = 1;i <= T;i++) solve(i);return 0;
}