[题解]P13292 [GCJ 2013 #1C] Pogo

· · 题解

更好的阅读体验

思路

要求步数最少的操作方案，先考虑操作 n 步能走到 (x,y) 的条件：

不妨猜测上面两个必要条件加起来是充要的，考虑归纳法证明：

  • 当 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 long

using 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;
}