TopCoder SRM 604: TorusSailing

問題文とは逆に (x, y) からスタートして 1, 9, 27 ... の直進移動で (0, 0) に移動できるかどうかを考える。

2ステップ以降は、3の倍数分しか移動できないため 1ステップ目で x, y が両方とも 3 の倍数になるように移動しなくてはならない。

x と y が両方とも 3 の倍数ではない場合は、x と y を両方移動する必要があり、それは 1ステップでできないため、"Impossble" になる。

それ以外の場合は、3 の倍数になるように x または y を移動することで (3 * p, 3 * q) で表される座標に移動できる。

あとは 3, 9, 27 ... の直進移動で (3 * p, 3 * q) から (0, 0) に到達できるかを判定する。ここで全体の座標を 3 で割ると "1, 3, 9 ... の直進移動で (p, q) から (0, 0) に到達できるを判定する" 問題となり、これは元々の問題になることから再帰的に処理できる。

public class PowerOfThree {
    public string ableToGet(int x, int y) {
        if (x == 0 && y == 0) return "Possible";
        if (x < 0) x = -x;
        if (y < 0) y = -y;
        if (x % 3 == 1) x--;
        else if (x % 3 == 2) x++;
        else if (y % 3 == 1) y--;
        else if (y % 3 == 2) y++;
        else return "Impossible";
        if (x % 3 != 0 || y % 3 != 0)
            return "Impossible";
        return ableToGet(x / 3, y / 3);
    }
}