- 原点から始めて (x, y) に行きたい。kステップ目は 3^(k-1) だけ上下左右どれかに必ず移動する。(x, y) に行けるかどうか求める。
- -1,000,000,000≦x, y≦1,000,000,000
- 最初にどっちに行くかは決められないような気がする(終了後→余りを考えると決められるらしいと判明)
- なので、逆に x, y から移動距離 3^K で始めて原点に戻る方向で考えてみる
- 原点より上にいて上下どっちかに行く場合、(移動量が1/3になってくので)上に進むと以後どんなに下に戻っても上に進んだ距離の半分以下の場所にはこれない。
- (初項1/3,公比1/3の等比数列の和＜1/2)
- なので原点より上にいて上下に進むなら下に行くしかない。横方向も同じ。
- なので、各ステップで上下に進むか左右に進むかの２通り選べばよい
- 1,000,000,000＜3^19 で、最初に進んだ距離の半分以上は戻れないことを考えると 20 ステップあれば終わるはず。
- 余裕(?)を見て 21 として, K in [0, 21] のそれぞれに対して 2^K 通りの探索で間に合うはず。
class PowerOfThree {
public:
bool f(ll X, ll Y, ll step) {
if(X==0 && Y==0 && step==0) return true;
if(step==0) return false;
return f(X+(X>0?-1:1)*step, Y, step/3) || f(X, Y+(Y>0?-1:1)*step, step/3);
}
string ableToGet(int x, int y) {
bool ans=false;
if(x==0 && y==0) return "Possible";
REP(k, 22) {
ll step=1;
REP(i, k) step*=3;
ans = ans || f(x, y, step);
if(ans) break;
}
return ans ? "Possible" : "Impossible";
}
};
- あとで
- そうか余りに注目すると逆にしなくてもどっちに進むべきか or 不可能か分かるのか。
