uva 679 - Dropping Balls Solution

uva 679 - Dropping Balls Solution

Algorithm:

1. convert (position-1)  to binary and store it to a string.
2. make the binary string length equal to the (depth-1) by adding zero(0) at start of the string.
3. reverse the binary string.
4. convert binary string to integer + power(2,depth-1).

Example:

depth=7;
position=4;

covert 4-1= 3 to binary. binary string is 11.
make the string length 7-1=6 by adding 0. Updated string 000011.
reverse the binary string and string is now 110000
convert binary string(110000) to integer. value is 48.
calculate power_value=pow(2,7-1)=pow(2,6)=64.
Answer is = 48 + 64=112.

Code in C++:

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

string convertDecimalToBinary(int num){
string result;
while(num!=0){
if(num%2==1)
result.insert(0,1,'1');
else
result.insert(0,1,'0');
num=num/2;
}
return result;
}


int convertBinaryToDecimal(string &num){
int i,len=num.length()-1,result=0,mul=1;
if(num[len]=='1')
result=1;
for(i=len-1;i>=0;i--){
mul=mul*2;
if(num[i]=='1'){
result+=mul;
}
}
return result;
}



int main(){
string str;
int n,d,p,len,val,i,mul=1,power0f2[21];
for(i=1;i<=20;i++){
power0f2[i]=mul;
mul*=2;
}
cin>>n;
while(n--){
cin>>d>>p;
str=convertDecimalToBinary(p-1);
len=str.length();
if(len<d-1){
str.insert(0,d-len-1,'0');
}
reverse(str.begin(),str.end());
val=convertBinaryToDecimal(str);
cout<<val+power0f2[d]<<endl;
}
cin>>n;

return 0;
}