MT2042 硬币塔

#include <bits/stdc++.h>
using namespace std;
const long long int N = 45;
long long int n, i;
long long int coin[N], gold[N];
 
long long int f(long long int n, long long int i) // 求到第n级硬币塔
{
    if (i == 0) // 0层
        return 0;
    if (n == 0)
        return 1; // 0级
    if (i <= 1)
        return 0;             //<=1层
    if (i <= coin[n - 1] + 1) // 在下面的k-1级硬币塔中
        return f(n - 1, i - 1);
    if (i <= coin[n - 1] + 1 + n) // 在中间n个金币中
        return gold[n - 1] + i - coin[n - 1] - 1;
    if (i <= 2 * coin[n - 1] + 1 + n) // 在上面的k-1级硬币塔中
        return gold[n - 1] + n + f(n - 1, i - coin[n - 1] - n - 1);
    return gold[n]; // i大于硬币塔层数
}
 
int main()
{
    cin >> n >> i;
 
    // coin[k]=2*coin[k-1]+k+2 可以看成5层
    // gold[k]=2*gold[k-1]+k
    // gold[0]=1;
    coin[0] = gold[0] = 1;
    for (long long int k = 1; k <= n; k++)
    {
        coin[k] = 2 * coin[k - 1] + k + 2;
        gold[k] = 2 * gold[k - 1] + k;
    }
    cout << f(n, i);
    return 0;
}