Problem B
Out of Sorts
Ann Logan is fascinated with finite sequences of integers.
She is particularly interested in sequences of the form
-
, -
, , , and are positive integer constants, -
is a non-negative integer constant, and -
all
values are unique.
For example, if
Ann wants to be able to quickly determine, for any integer
value, whether or not it appears within a finite sequence of
this form. Given values of
-
Generate the sequence
and store it in an array. -
Sort the array.
-
Perform a binary search of the array for each integer of interest to her.
Ann’s search algorithm, while not the most efficient possible, is pretty straightforward and understandable to anyone familiar with binary search: after calculating the midpoint mid at each step of the calculation (using mid = (low+high)/2), she first checks whether or not the value at location mid is equal to the search value x. If not, she then narrows the search according to whether x is strictly less than or strictly greater than the value at location mid.
Unfortunately, Ann is absent-minded and she lost her list of
steps. She managed to remember the first and last step, but
…she forgot to sort the array before performing her binary
search! Needless to say, this means that many values that are
in the (unsorted) array will not be found by a binary search,
although surprisingly some can. In the example above, both
Input
Input consists of a line containing five integers
Output
Output the number of sequence values that could be found using Ann’s version of binary search, assuming she forgot to sort the sequence.
Sample Input 1 | Sample Output 1 |
---|---|
5 8 1 3 3 |
2 |
Sample Input 2 | Sample Output 2 |
---|---|
6 10 1234567891 1 1234567890 |
6 |