ZOJ Problem Set - 3162
Wyest and Winsty are two lazy kids who'd rather eat some snacks in the dorm than go to the dining hall. Wyest, however, wants to be healthy occasionally, then she'd persuade Winsty to have meals together, with the reason "Vitta will love you more if you grow some muscle". Since Wyest likes it uncertain, she comes up with a way to decide whether they should step out of their dorms at dinner time.
They randomly choose two positive integers x, y and decide whether they're going or not by the low <y mod l>-th bit of x (where l is the length of x in binary representation, and define the lowest bit to be the zeroth). If the bit is an '1', they get up to the dining hall, or they just continue staying in front of their computers. Now Wyest wonders what the probability of their having meals is, if they give a range to x.
The first line of input is the number of test cases T, then T lines follow, each is a test case with two positive integers a and b, both not larger than 50,000,000. a is guaranteed not to be larger than b. x is randomly chosen from the interval [a,b]. No limit on y.
For each case in the input, output a separate line containing the probability (accurate to 6 fractional digits) of getting an '1' in the way described above and clarified below.
1 4 5
In the sample, x can be 4 or 5 ('100' or '101') with equal possibility, so the probability of getting an '1' is 1/2 * 1/3 + 1/2 * 2/3 = 1/2.
Author: WANG, Yuting
Source: ZOJ Monthly, February 2009