TopCoder SRM604: PowerOfThreeEasy

1ステップ後は、３倍数分の移動しかできないので、x, yともに３の倍数になるように必要がある。このことを利用して再帰的に処理できる。

public class PowerOfThreeEasy {
    public string ableToGet(int x, int y) {
        while (x != 0 || y != 0) {
            if (x % 3 == 1) {
                x--;
            } else if (y % 3 == 1) {
                y--;
            } else
                return "Impossible";
            
            if (x % 3 != 0 || y % 3 != 0)
                return "Impossible";

            x /= 3; y /= 3;
        }
        return "Possible";
    }
}