a249. 00679 - Dropping Balls -- UVa679 | From: [115.43.237.155] | 發表日期 : 2024-03-11 16:57

#include<iostream>

#include<math.h> 

#include <stdlib.h>

using namespace std;

 

int main(){

int times;

scanf("%d",&times);

long depth, nodec, ballno, res, position; //代表樹的深度，點數，目標球號碼，輸出結果，過程中球的位置 

bool *tree;

for(int runtimes=0;runtimes<times;runtimes++){

    scanf("%d",&depth);

    nodec = pow(2,depth); nodec--; //求出深度 

    tree = (bool*)malloc(sizeof(bool)*nodec);

    for(int i=0;i<nodec;i++){    //初始nodes = false 

       tree[i] = false;

    }

 

   scanf("%d",&ballno);

   for(int i=0;i<ballno;i++){       //放球 

      position=0;

      while((position*2)<nodec){

         if(tree[position] == true){ //兩種情況分別討論 

            tree[position]=false;

            position = position*2+1; //往右子走 

         }

         else{

            tree[position]=true;

            position = position*2; //往左子走

         }

      }

      res=position;

   }

   printf("%d\n",res);

   free(tree);

}

    return 0;

}