#include <stdlib.h>
#include <cmath>
#include <iostream>
using namespace std;
 
int rand_small()
{
    return (rand() >> 7) & 0xff;
}
 
#define RAND_MAX_SMALL 255
 
int rangeRandomAlg1 (int min, int max)
{
    static const double s_invRandMax = 1.0/((double)RAND_MAX_SMALL + 1.0);
    return min + (int)(((double)(max + 1 - min))*rand_small()*s_invRandMax);
}
 
int rangeRandomAlg2 (int min, int max)
{
    int n = max - min + 1;
    int remainder = RAND_MAX_SMALL % n;
    int x;
    do
    {
        x = rand_small();
    } while (x >= RAND_MAX_SMALL - remainder);
    return min + x % n;
}
 
int main ()
{
    static const int s_numBuckets = 10; // the number of "buckets"
    static const int s_numBalls = 1000000; // the number of "balls"
    int buckets[s_numBuckets];
    double idealProbPerBucket = 1.0/s_numBuckets;
    double maxDevFromIdealProb;
 
    // Testing algorithm 1
    cout << "Testing with floating-point mapping:" << endl;
    for (int i = 0; i < s_numBuckets; i++)
    {
        buckets[i] = 0;
    }
    srand(0);
    for (int i = 0; i < s_numBalls; i++)
    {
        buckets[rangeRandomAlg1(0, s_numBuckets - 1)]++;
    }
    maxDevFromIdealProb = -1.0;
    for (int i = 0; i < s_numBuckets; i++)
    {
        double prob = ((double)buckets[i])/s_numBalls;
        cout << "Probability for bucket #" << i << ": " << prob << endl;
 
        double devFromIdealProb = fabs(prob - idealProbPerBucket);
        if ( devFromIdealProb > maxDevFromIdealProb )
        {
            maxDevFromIdealProb = devFromIdealProb;
        }
    }
    cout << ">>> Maximum deviation from the ideal probability: " << maxDevFromIdealProb << endl;
    cout << endl;
 
    // Testing algorithm 2
    cout << "Testing with Java's algorithm:" << endl;
    for (int i = 0; i < s_numBuckets; i++)
    {
        buckets[i] = 0;
    }
    srand(0);
    for (int i = 0; i < s_numBalls; i++)
    {
        buckets[rangeRandomAlg2(0, s_numBuckets - 1)]++;
    }
    maxDevFromIdealProb = -1.0;
    for (int i = 0; i < s_numBuckets; i++)
    {
        double prob = ((double)buckets[i])/s_numBalls;
        cout << "Probability for bucket #" << i << ": " << prob << endl;
 
        double devFromIdealProb = fabs(prob - idealProbPerBucket);
        if ( devFromIdealProb > maxDevFromIdealProb )
        {
            maxDevFromIdealProb = devFromIdealProb;
        }
    }
    cout << ">>> Maximum deviation from the ideal probability: " << maxDevFromIdealProb << endl;
 
    return 0;
}

I2luY2x1ZGUgPHN0ZGxpYi5oPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDxpb3N0cmVhbT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCByYW5kX3NtYWxsKCkKewogICAgcmV0dXJuIChyYW5kKCkgPj4gNykgJiAweGZmOwp9CgojZGVmaW5lIFJBTkRfTUFYX1NNQUxMIDI1NQoKaW50IHJhbmdlUmFuZG9tQWxnMSAoaW50IG1pbiwgaW50IG1heCkKewogICAgc3RhdGljIGNvbnN0IGRvdWJsZSBzX2ludlJhbmRNYXggPSAxLjAvKChkb3VibGUpUkFORF9NQVhfU01BTEwgKyAxLjApOwogICAgcmV0dXJuIG1pbiArIChpbnQpKCgoZG91YmxlKShtYXggKyAxIC0gbWluKSkqcmFuZF9zbWFsbCgpKnNfaW52UmFuZE1heCk7Cn0KCmludCByYW5nZVJhbmRvbUFsZzIgKGludCBtaW4sIGludCBtYXgpCnsKICAgIGludCBuID0gbWF4IC0gbWluICsgMTsKICAgIGludCByZW1haW5kZXIgPSBSQU5EX01BWF9TTUFMTCAlIG47CiAgICBpbnQgeDsKICAgIGRvCiAgICB7CiAgICAgICAgeCA9IHJhbmRfc21hbGwoKTsKICAgIH0gd2hpbGUgKHggPj0gUkFORF9NQVhfU01BTEwgLSByZW1haW5kZXIpOwogICAgcmV0dXJuIG1pbiArIHggJSBuOwp9CgppbnQgbWFpbiAoKQp7CiAgICBzdGF0aWMgY29uc3QgaW50IHNfbnVtQnVja2V0cyA9IDEwOyAvLyB0aGUgbnVtYmVyIG9mICJidWNrZXRzIgogICAgc3RhdGljIGNvbnN0IGludCBzX251bUJhbGxzID0gMTAwMDAwMDsgLy8gdGhlIG51bWJlciBvZiAiYmFsbHMiCiAgICBpbnQgYnVja2V0c1tzX251bUJ1Y2tldHNdOwogICAgZG91YmxlIGlkZWFsUHJvYlBlckJ1Y2tldCA9IDEuMC9zX251bUJ1Y2tldHM7CiAgICBkb3VibGUgbWF4RGV2RnJvbUlkZWFsUHJvYjsKCiAgICAvLyBUZXN0aW5nIGFsZ29yaXRobSAxCiAgICBjb3V0IDw8ICJUZXN0aW5nIHdpdGggZmxvYXRpbmctcG9pbnQgbWFwcGluZzoiIDw8IGVuZGw7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IHNfbnVtQnVja2V0czsgaSsrKQogICAgewogICAgICAgIGJ1Y2tldHNbaV0gPSAwOwogICAgfQogICAgc3JhbmQoMCk7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IHNfbnVtQmFsbHM7IGkrKykKICAgIHsKICAgICAgICBidWNrZXRzW3JhbmdlUmFuZG9tQWxnMSgwLCBzX251bUJ1Y2tldHMgLSAxKV0rKzsKICAgIH0KICAgIG1heERldkZyb21JZGVhbFByb2IgPSAtMS4wOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBzX251bUJ1Y2tldHM7IGkrKykKICAgIHsKICAgICAgICBkb3VibGUgcHJvYiA9ICgoZG91YmxlKWJ1Y2tldHNbaV0pL3NfbnVtQmFsbHM7CiAgICAgICAgY291dCA8PCAiUHJvYmFiaWxpdHkgZm9yIGJ1Y2tldCAjIiA8PCBpIDw8ICI6ICIgPDwgcHJvYiA8PCBlbmRsOwoKICAgICAgICBkb3VibGUgZGV2RnJvbUlkZWFsUHJvYiA9IGZhYnMocHJvYiAtIGlkZWFsUHJvYlBlckJ1Y2tldCk7CiAgICAgICAgaWYgKCBkZXZGcm9tSWRlYWxQcm9iID4gbWF4RGV2RnJvbUlkZWFsUHJvYiApCiAgICAgICAgewogICAgICAgICAgICBtYXhEZXZGcm9tSWRlYWxQcm9iID0gZGV2RnJvbUlkZWFsUHJvYjsKICAgICAgICB9CiAgICB9CiAgICBjb3V0IDw8ICI+Pj4gTWF4aW11bSBkZXZpYXRpb24gZnJvbSB0aGUgaWRlYWwgcHJvYmFiaWxpdHk6ICIgPDwgbWF4RGV2RnJvbUlkZWFsUHJvYiA8PCBlbmRsOwogICAgY291dCA8PCBlbmRsOwoKICAgIC8vIFRlc3RpbmcgYWxnb3JpdGhtIDIKICAgIGNvdXQgPDwgIlRlc3Rpbmcgd2l0aCBKYXZhJ3MgYWxnb3JpdGhtOiIgPDwgZW5kbDsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgc19udW1CdWNrZXRzOyBpKyspCiAgICB7CiAgICAgICAgYnVja2V0c1tpXSA9IDA7CiAgICB9CiAgICBzcmFuZCgwKTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgc19udW1CYWxsczsgaSsrKQogICAgewogICAgICAgIGJ1Y2tldHNbcmFuZ2VSYW5kb21BbGcyKDAsIHNfbnVtQnVja2V0cyAtIDEpXSsrOwogICAgfQogICAgbWF4RGV2RnJvbUlkZWFsUHJvYiA9IC0xLjA7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IHNfbnVtQnVja2V0czsgaSsrKQogICAgewogICAgICAgIGRvdWJsZSBwcm9iID0gKChkb3VibGUpYnVja2V0c1tpXSkvc19udW1CYWxsczsKICAgICAgICBjb3V0IDw8ICJQcm9iYWJpbGl0eSBmb3IgYnVja2V0ICMiIDw8IGkgPDwgIjogIiA8PCBwcm9iIDw8IGVuZGw7CgogICAgICAgIGRvdWJsZSBkZXZGcm9tSWRlYWxQcm9iID0gZmFicyhwcm9iIC0gaWRlYWxQcm9iUGVyQnVja2V0KTsKICAgICAgICBpZiAoIGRldkZyb21JZGVhbFByb2IgPiBtYXhEZXZGcm9tSWRlYWxQcm9iICkKICAgICAgICB7CiAgICAgICAgICAgIG1heERldkZyb21JZGVhbFByb2IgPSBkZXZGcm9tSWRlYWxQcm9iOwogICAgICAgIH0KICAgIH0KICAgIGNvdXQgPDwgIj4+PiBNYXhpbXVtIGRldmlhdGlvbiBmcm9tIHRoZSBpZGVhbCBwcm9iYWJpbGl0eTogIiA8PCBtYXhEZXZGcm9tSWRlYWxQcm9iIDw8IGVuZGw7CgogICAgcmV0dXJuIDA7Cn0=