问题 D: cats 的二分答案
内存限制：512 MB
时间限制：2 S
题面：传统
评测方式：文本比较
上传者：
提交：3
通过：3
题目描述
cats 刚刚开始学习二分答案，写出了下面这段代码（以下给出伪代码，在题目的末尾会提供
C/C++，Python，Java 语言的具体代码）
给出的数组 a 下标范围为 [1, n]，且
ai =
(
1 (i ∈ [1, n))
2 (i = n)
cats 知道 n ∈ [l, r]，他希望通过以上这段代码找出 n 的值。可以发现这段代码有访问越界下标的可能，
访问越界下标 i > n 时，会得到 ai = 0。但是在一次程序运行过程中，如果访问越界下标超过 k 次，
程序就会崩溃。现在你需要求出有多少不同的 n（n ∈ [l, r]）可以让程序在不崩溃的情况下得到正确结
果。
输入格式
第一行一个整数 T（1 ≤ T ≤ 10^3），表示测试数据的组数。
接下来 T 行，每行三个整数 l, r, k（1 ≤ l ≤ r ≤ 10^18
, 0 ≤ k ≤ 10^18），表示 n 的范围和程序在不崩溃的
情况下访问越界下标次数的上限。
输出格式
对于每组测试数据，输出一个整数，表示满足条件的不同的 n 的个数。
输入样例 复制
3
1 100 0
1 100 1
1 100 2输出样例 复制
7
28
61数据范围与提示
C/C++：
long long BinarySearch(long long l,long long r,int *a)
{
while(l<=r)
{
long long mid=(l+r)/2;
int val=a[mid];
if(val==2)
{
return mid;
}
if(val==1)
{
l=mid+1;
}
else
{
r=mid-1;
}
}
return -1;
}
Python： def BinarySearch(l, r, a):
while l <= r:
mid = (l + r) // 2
val = a[mid]
if val == 2:
return mid
elif val == 1:
l = mid + 1
else:
r = mid - 1
return -1
Java： public class BinarySearch
{
public static long binarySearch(long l, long r, int[] a)
{
while(l<=r)
{
long mid=(l+r)/2;
int val=a[mid];
if(val==2)
{
return mid;
}
if(val==1)
{
l=mid+1;
}
else
{
r=mid-1;
}
}
return -1;
}
}
