Find the probability of getting a 1-bit number ?

By | 19.02.2017

Find the probability of getting a 1bit number ?


Find the probability of getting a 1-bit number after the following procedure is followed:

Initially a number x is chosen at random in a given range .After this we again choose a bit from x randomly?

Find the expected number of bit 1s if we randomly choose a number x in the given range?


Explanation 


 Input Format

The first line of input is the number of test cases T. Each test cases is a line contains 2 integers A and B separated by a space.

Output Format

For each test case output a line containing 2 float numbers separated by a space. The first one is the probability and the second one is the expected number. You should output the number accurate to 5 fractional digits.

Constraints

1 <= T <= 200

1 <= A <= B <= 10^10

Sample Input

1

2 4

Sample Output

0.61111

1.33333

Explanation

(10) (11) (100)

(1) So we got a one in :

(1/3)(1/2)+(1/3)(1/1)+(1/3)*(1/3)=(11/18)

(2) The expected 1 we have is

(1)(1/3)+(2)(1/3)+(1)*(1/3)=(4/3)

Time Limit:3.0 sec(s) for each input file.

Memory Limit:256 MB

Source Limit:1024 KB


SOURCE CODE ::

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

#define mygc(c) (c)=getchar_unlocked()
void reader(int *x)
{
    int k,m=0;*x=0;
    for(;;)
        {
            mygc(k);
        if(k=='-')
            {m=1;
        break;
        }
        if('0'<=k&&k<='9')
            {
                *x=k-'0';
        break;
        }
    }
        for(;;)
            {
                mygc(k);
        if(k<'0'||k>'9')
            break;
        *x=(*x)*10+k-'0';
        }
        if(m)(*x)=-(*x);
    }
    
void reader(ll *x)
{
    int k,m=0;*x=0;
    for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}
    for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);
}

int T;
ll A, B;

ll cnt(ll A){
  ll p, all, rest;
  ll res = 0;

  for(p=1;;p*=2){
    if(A < p) break;
    all = (A/(2*p));
    rest = (A%(2*p));
    res += all * p;
    if(rest >= p) res += rest - p;
  }

  return res;
}

ll cntRange(ll A, ll B){
  return cnt(B+1) - cnt(A);
}

int main(){
  int i, j, k;
  ll st, ed, dig, r, tmp;
  double res1, res2;

  reader(&T);
  while(T--){
    reader(&A);
    reader(&B);
    res1 = res2 = 0;

    st = ed = dig = 1;
    for(;;){
      if(st > B) break;

      if(max(st,A) <= min(ed,B)){
        tmp = cntRange(max(st,A), min(ed,B));
        r = min(ed,B) - max(st,A) + 1;

        res1 += tmp / (double)dig;
        res2 += tmp;
      }

      st = st*2;
      ed = st*2-1;
      dig++;
    }

    res1 /= (B-A+1);
    res2 /= (B-A+1);
    printf("%.5f %.5f\n",res1,res2);
  }

  return 0;
}

 

OUTPUT : :

 

1

2 4

0.61111

1.33333

 

0 0 votes
Article Rating
Category: Tricky Q Tags:

About Tunde A

My name is Tunde Ajetomobi, a Tech Enthusiast and Growth Hacker. I enjoy creating helpful content that solves problem across different topics. Codezclub is my way of helping young aspiring programmers and students to hone their skills and find solutions on fundamental programming languages.

Subscribe
Notify of
guest

0 Comments
Inline Feedbacks
View all comments