Binary Search#4117
The program fragment below performs a binary search for an integer number in an array:
Before BinarySearch was called, was set to some integer number from to inclusive and array was filled with integer values.
It is known that the procedure has terminated with the message "Found item i = XXX in L = XXX comparisons" with some known values of and .
Your task is to write a program that finds all possible values of that could lead to such a message. However, the number of possible values of can be quite large. Thus, you are asked to group all consecutive s into intervals and write down only the first and last value in each interval.
The input consists of a single line with two integers and (0 \leq i < 10000 and 1 \leq L \leq 14), separated by a space.
On the first line of the output, write the single integer representing the total number of intervals for possible values of . Then lines shall follow, listing those intervals in ascending order. Each line shall contain two integers A_i and B_i (A_i \leq B_i) separated by a space, representing the first and last value of the interval.
If there are no possible values of , then the output shall contain the single .
Esempio 1