Soluție HackerRank pentru Random Integers Random Bits, subdomeniul Probability, în C++14. Include cerința formatată, exemple, explicația pașilor și cod…

  • Problemă: Random Integers Random Bits
  • Domeniu: Probability
  • Limbaj: C++14

Challenge: Random Integers Random Bits

Subdomeniu: Probability (probability)

Scor cont: 60.0 / 60

Submission status: Accepted

Submission score: 1.0

Submission ID: 464756904

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/rirb/problem

Cerință

Given an integer range [A,B],

1. What’s the probability to get a 1-bit if we first randomly choose a number x in the range and then randomly choose a bit from x?
2. What’s the expected number of bit 1s if we randomly choose a number x in the range?

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)

Cod sursă

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

using i128 = __int128_t;
using u128 = __uint128_t;

static inline i128 prefixPopcount(unsigned long long n) {
    // sum_{x=0..n} popcount(x)
    i128 total = 0;
    u128 nn = (u128)n + 1; // count of numbers
    for (int b = 0; b < 64; ++b) {
        u128 half = (u128)1 << b;
        u128 cycle = half << 1;
        if (half > nn && b > 0) {
            // for larger b, term will be 0
            if (((u128)1 << b) > nn && ((u128)1 << (b + 1)) > nn) {
                // keep loop simple; break when half exceeds nn and no remainder can add
            }
        }

        u128 full = nn / cycle;
        u128 rem = nn % cycle;
        u128 ones = full * half + (rem > half ? rem - half : 0);
        total += (i128)ones;

        if (half > nn) break;
    }
    return total;
}

static inline long double prefixRatio(unsigned long long n) {
    // sum_{x=1..n} popcount(x) / bitlen(x)
    if ((long long)n <= 0) return 0.0L;

    long double ans = 0.0L;
    for (int L = 1; L <= 64; ++L) {
        u128 l = (L == 1 ? 1 : ((u128)1 << (L - 1)));
        if (l > (u128)n) break;
        u128 r = ((u128)1 << L) - 1;
        if (r > (u128)n) r = (u128)n;

        unsigned long long ll = (unsigned long long)l;
        unsigned long long rr = (unsigned long long)r;

        i128 ones = prefixPopcount(rr) - prefixPopcount(ll - 1);
        ans += (long double)ones / (long double)L;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    cout.setf(std::ios::fixed);
    cout << setprecision(5);

    while (T--) {
        unsigned long long A, B;
        cin >> A >> B;

        unsigned long long cnt = B - A + 1;

        i128 sumOnes = prefixPopcount(B) - (A == 0 ? 0 : prefixPopcount(A - 1));
        long double expected = (long double)sumOnes / (long double)cnt;

        long double sumRatio = prefixRatio(B) - (A == 0 ? 0.0L : prefixRatio(A - 1));
        long double prob = sumRatio / (long double)cnt;

        cout << (double)prob << ' ' << (double)expected << '\n';
    }

    return 0;
}
HackerRank Probability – Random Integers Random Bits