# B类
# 题目链接:
https://abc115.contest.atcoder.jp/tasks/abc115_d
# 原题:
**Problem Statement**
In some other world, today is Christmas.
Mr. Takaha decides to make a multi-dimensional burger in his party. A level-L burger (L is an integer greater than or equal to 0) is the following thing:
A level-0 burger is a patty.
A level-L burger (L≥1) is a bun, a level-(L−1) burger, a patty, another level-(L−1) burger and another bun, stacked vertically in this order from the bottom.
For example, a level-1 burger and a level-2 burger look like BPPPB and BBPPPBPBPPPBB (rotated 90 degrees), where B and P stands for a bun and a patty.
The burger Mr. Takaha will make is a level-N burger. Lunlun the Dachshund will eat X layers from the bottom of this burger (a layer is a patty or a bun). How many patties will she eat?
**Constraints**
1≤N≤50
1≤X≤( the total number of layers in a level-N burger )
N and X are integers.
**输入格式:**
Input is given from Standard Input in the following format:
N X
**输出格式:**
Print the number of patties in the bottom-most X layers from the bottom of a level-N burger.
**输入样例1:**
2 7
**输出样例1:**
4
There are 4 patties in the bottom-most 7 layers of a level-2 burger (BBPPPBPBPPPBB).
**输入样例2:**
1 1
**输出样例2:**
0
The bottom-most layer of a level-1 burger is a bun.
**输入样例3:**
50 4321098765432109
**输出样例3:**
2160549382716056
A level-50 burger is rather thick, to the extent that the number of its layers does not fit into a 32-bit integer.
------------
# 题意:
吃汉堡,汉堡的规律已在题目中给出。求吃了N层的时候吃了多少层肉饼
# 思路:
孔妹妹的思路,将汉堡分成五个部分
B(L-1)P(L-1)B
当前N级汉堡的总层数是通过递归求出,递归方程:
(N-1)*2+3 if(n>1)
5 if(n==1)
当前N级汉堡的肉数也是通过递归求出的,递归方程:
(N-1)*2+1 if(n>1)
3 if(n==1)
如果现在X落在第二第四部分,递归到下一层,如此下去,总能找到落在第一第三第五层,就可直接输出答案了。
# AC代码:
```
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#include<algorithm>
#include<queue>
typedef long long ll;
#include<vector>
#define cin(n) scanf("%lld",&(n))
#define cout(n) printf("%lld",(n))
#define couc(c) printf("%c",(c))
#define coutn printf("\n")
#define cout_ printf(" ")
#define debug() printf("haha\n")
const int MAXN= 1e6 + 5 ;
ll t;
ll n,k;
ll hamburger[MAXN]={1,5};
ll meat[MAXN]={1,3};
ll onemeat[MAXN]={0,0,1,2,3,3};
ll rou=3;
ll now=5;
ll an;
ll findmeat(ll x,ll m)
{
if(m==1)
return onemeat[x];
if(x==1)
return 0;
else if(x<hamburger[m]/2+1)
return findmeat(x-1,m-1);
else if(x==hamburger[m]/2+1)
return meat[m-1]+1;
else if(x>hamburger[m]/2+1&&x!=hamburger[m])
return meat[m-1]+1+findmeat(x-hamburger[m]/2-1,m-1);
else if(x==hamburger[m])
return meat[m];
}
int main()
{
cin(n);
cin(k);
for(int i=2;i<=n;i++)
{
meat[i]=meat[i-1]*2+1;
hamburger[i]=hamburger[i-1]*2+3;
}
ll ans=findmeat(k,n);
cout(ans);
coutn;
return 0;
}
```