Find the probability of getting a 1–bit 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 : :

0 0 votes

Article Rating