5935 小球

5935 小球

 

时间限制: 2 s

空间范围: 1五千 KB

标题等级 : 黄金 戈尔德

 

 

 

 

题材叙述 Description

无数的小球三个2个的从一棵满二叉树上掉下来组成FBT(Full Binary
Tree,满二叉树),每暂时刻,1个正在下落的球第3个访问的是是非非叶子节点。然后继续下落时,或然走右子树,大概走左子树,直到访问到叶子节点。决定球运动方向的是种种节点的布尔值。最初,全体的节点都以FALSE,当访问到七个节点时,假如这些节点是FALSE,则这些球把它成为TRUE,然后从左子树走,继续它的旅程。若是节点是TRUE,则球也会改变它为FALSE,而接下去从右子树走。满二叉树的标记方法如下图。

因为具备的节点最初为FALSE,所以首先个球将会访问节点1,节点2和节点4,转变节点的布尔值后在在节点8停下。第2个球将会访问节点1、三,6,在节点12悬停。鲜明地,第多个球在它截至此前,会造访节点一,2、5,在节点10停歇。
  以后你的职务是,给定FBT的深度D,和I,表示第I个小球降低,你可以假定I不超越给定的FBT的叶子数,写二个先后求小球为止时的纸牌序号。

输入描述 Input Description

输入文件仅一行包罗八个用空格隔开的平头D和I。其中2<=D<=20,1<=I<=524288。

出口描述 Output Description

对应输出第I个小球下跌截至时的纸牌序号。

样例输入 Sample Input

4 2

样例输出 Sample Output

1 2

数据范围及提醒 Data Size & Hint

2<=D<=20,1<=I<=524288。

5935 小球

 

时间限制: 2 s

空间范围: 1六千 KB

标题等级 : 黄金 戈尔德

 

 

 

 

题目叙述 Description

无数的小球3个3个的从一棵满二叉树上掉下来组成FBT(Full Binary
Tree,满二叉树),每一虚岁月,二个正在降低的球第多少个访问的黑白叶子节点。然后继续降低时,只怕走右子树,恐怕走左子树,直到访问到叶子节点。决定球运动方向的是各种节点的布尔值。最初,全数的节点都以FALSE,当访问到贰个节点时,尽管这几个节点是FALSE,则那些球把它变成TRUE,然后从左子树走,继续它的旅程。即使节点是TRUE,则球也会转移它为FALSE,而接下去从右子树走。满二叉树的标记方法如下图。

因为全数的节点最初为FALSE,所以首先个球将会访问节点1,节点2和节点4,转变节点的布尔值后在在节点8截止。第壹,个球将会造访节点一,三,6,在节点12停下。分明地,第多个球在它甘休此前,会造访节点一,二,5,在节点10甘休。
  未来您的天职是,给定FBT的深度D,和I,表示第I个小球下跌,你可以假定I不当先给定的FBT的叶子数,写五个程序求小球为止时的叶子序号。

输入描述 Input Description

输入文件仅一行包涵多少个用空格隔开的平头D和I。其中2<=D<=20,1<=I<=524288。

出口描述 Output Description

对应输出第I个小球降低为止时的纸牌序号。

样例输入 山姆ple Input

4 2

样例输出 萨姆ple Output

1 2

多少范围及提醒 Data Size & Hint

2<=D<=20,1<=I<=524288。

分类标签 Tags 点此展开

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 bool a[10000001];
 6 int main()
 7 {
 8     int n,m;
 9     scanf("%d%d",&n,&m);
10     double p=pow(2,n);
11     int flag=0;// 表示最后一次的变换情况 
12     for(int i=1;i<=m;i++)
13     {
14         int now=0;//表示正在访问的节点
15         
16         while(now<=(int)p-1)
17         {
18             if(a[now]==0)
19             {
20                 a[now]=1;
21                 now=2*now;    
22                 flag=1;
23             }    
24             else
25             {
26                 a[now]=0;
27                 now=2*now+1;
28                 flag=2;
29             }
30         } 
31         if(i==m)
32         {
33             if(flag=1)
34             printf("%d",now/2);
35             else
36             printf("%d",now/2-1);
37         }
38     }
39     return 0;
40 }

 

分拣标签 Tags 点此开展

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 bool a[10000001];
 6 int main()
 7 {
 8     int n,m;
 9     scanf("%d%d",&n,&m);
10     double p=pow(2,n);
11     int flag=0;// 表示最后一次的变换情况 
12     for(int i=1;i<=m;i++)
13     {
14         int now=0;//表示正在访问的节点
15         
16         while(now<=(int)p-1)
17         {
18             if(a[now]==0)
19             {
20                 a[now]=1;
21                 now=2*now;    
22                 flag=1;
23             }    
24             else
25             {
26                 a[now]=0;
27                 now=2*now+1;
28                 flag=2;
29             }
30         } 
31         if(i==m)
32         {
33             if(flag=1)
34             printf("%d",now/2);
35             else
36             printf("%d",now/2-1);
37         }
38     }
39     return 0;
40 }