C++ 解决机器人移动问题：PowerOfThreeEasy

问题描述

Fox Ciel 有一个机器人，该机器人处在一个无限大的平面上。初始位置为坐标系原点 (0, 0)。机器人可以走若干步，从 0 开始给每步编号。

在每一步中，Fox Ciel 必须选择两个方向中的一个方向移动机器人：

右 (x 坐标增大)
上 (y 坐标增大)

在第 k 步，机器人必须在所选方向移动 2^k 个单位长度，且不允许跳过某一步。

现在给你两个整数 x 和 y。若机器人可以到达点 (x, y)，则输出 'Possible'，否则输出 'Impossible'。

输入格式

输入一行，包含两个整数 x 和 y。

输出格式

输出一行，包含一个字符串，表示是否能够到达。

样例输入

1 3

样例输出

Possible

样例输入

1 1

样例输出

Impossible

样例输入

3 0

样例输出

Impossible

数据规模和约定

0 <= x, y <= 1000000000

解题思路

首先，我们可以观察到机器人只能向右和向上移动，所以机器人的坐标 x 和 y 一定是非负整数。

其次，我们可以观察到机器人每一步移动后的坐标都会发生变化，变化量为 2 的幂次方。

所以，我们可以通过判断 x 和 y 是否都是 2 的幂次方来确定机器人是否能够到达目标点。

具体实现

#include <iostream>

using namespace std;

bool isPowerOfTwo(int n) {
    if (n <= 0) {
        return false;
    }
    return (n & (n - 1)) == 0;
}

int main() {
    int x, y;
    cin >> x >> y;

    if (isPowerOfTwo(x) && isPowerOfTwo(y)) {
        cout << "Possible" << endl;
    } else {
        cout << "Impossible" << endl;
    }

    return 0;
}

复杂度分析

判断一个数是否是 2 的幂次方的时间复杂度为 O(1)。所以总的时间复杂度为 O(1)。