牛客算法周周练6 [青蛙过河]

牛客算法周周练6 青蛙过河

思路

其实这就是一道数学规律题，我们不难发现。

当只有荷叶的时候，我们最多只能由((m + 1))个青蛙可以过河：(m)个青蛙先分别排类在荷叶上，然后再最后一个青蛙跳到目标石墩。

当存在一个石墩时，我们可以先让((m + 1))个青蛙跳到上面，去，然后我们还能再荷叶上放(m)个青蛙，最后在目标点上能放一只青蛙，这里就得到((m + 1) * 2)只青蛙可以跳过。

以此类推，每一个石墩我们都如同只有两个石墩一样处理，所以石墩上我们可以放(((1 << n) - 1) * (m + 1))只青蛙，最后的目标石墩我们还可以放((m + 1))只青蛙，所以总共就是((m + 1) * (1 << n))只青蛙。

代码

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    cout << (m + 1) * (1 << n) << "
";
    return 0;
}