###### tags: `UVa`
# UVa a249: 00679 - Dropping Balls
### 1st Ideas of solving a problem
> 1. List level 3 to level 5 all leaves,and identify the pattern in the collection of sequence.
> 2. I found that
> level 3 (4,6,5,7);
> level 4 (8,12,10,14)(9,13,11,14);
> level 5 (16,24,20,28,18,26,22,28)(17,25,21,29,19,27,23,29)
> .......
> The pattern ,which the sequence of the higher level is the sequence of the lower double and double plus 1, will be a circle by leaves number.
>3. I think it can use ==**recursion**== to finish this program. However I haven't find out how to do this

:::warning
Wrong version

//1.我列出從第三層開始找出規律，每組球球落點為(4,6,5,7)的倍數
//2.舉例 Level 3 共有4個leaf，球球出現順序為(4,6,9,7)做循環*2的0次方
//      Level 4 共有8個leaf，球球出現順序為(8,12,10,14,9,13,11,15)做循環，即為(4,6,9,7)做循環*2的1次方＋(4,6,9,7)做循環*2的1次方+1//   Level 5 共有16個leaf，即為(4,6,9,7)做循環*2的2次方＋(4,6,9,7)做循環*2的2次方+1＋(4,6,9,7)做循環*2的2次方+2＋(4,6,9,7)做循環*2的2次方+3
//3.遇到的bug第五組測資結果有問題ＱＱ
 
#include<stdio.h>
#include<math.h>
int main(){
int level,i,noNum,total;//total代表讀入的組數;level代表樹的高度；noNum代表落入的第幾顆球
scanf("%d",&total);
scanf("%d%d",&level,&noNum);
for(i=1;i<=total;i++){//用一個迴圈控制有幾組測資
int ans=0,n=0,start=0,leaf=0;//ans代表第noNum顆球落在哪個位子；start代表leaf號碼是4,6,5,7的規律中的倍數;leaf代表該compelet tree有多少leaf;n代表當noNum輸入後重複幾次後會落在第幾組的4,6,5,7,
if(level==2){//當level樹高為2時候直接判做作印出
if(noNum%2==0){
printf("3\n");
}
else if(noNum%2==1){
printf("2\n");
}
}
else{//當level樹高是3以上
start=pow(2,level-3);//start用來計算規律的倍數，例如level4 的leaf起始號碼為8(4*2的1倍)；level 5 的leaf起始號碼為16(4*2的2倍)
leaf=pow(2,level-1);//求出該compelet tree有多少leaf
n=(noNum%leaf)%4;//如果是第一組餘數為0如果是第一組餘數為0;
switch(n){
case 1:{ans=4*start+((noNum%leaf)/4);printf("%d\n",ans);}
case 2:{ans=6*start+((noNum%leaf)/4);printf("%d\n",ans);}
case 3:{ans=5*start+((noNum%leaf)/4);printf("%d\n",ans);}
case 0:{ans=7*start+((noNum%leaf)/4);printf("%d\n",ans);}
default:break;
}
 
 
}
scanf("%d%d",&level,&noNum);
}
 
 
return 0;
}

:::

### 2nd Ideas of solving a problem
>1. One feature of complete binary tree is left child is 2i; right child is 2i+1(if root==1)
>2. Therefore