cats 的二分答案

Problem Description

cats 刚刚开始学习二分答案，写出了下面这段代码（以下给出伪代码，在题目的末尾会提供 C/C++，Python，Java 语言的具体代码） 给出的数组 $a$ 下标范围为 $[1,n]$，且

$$a_i= \begin{cases} 1 & (i\in[1,n))\\ 2 & (i=n) \end{cases} $$

cats 知道 $n\in[l,r]$，他希望通过以上这段代码找出 $n$ 的值。可以发现这段代码有访问越界下标的可能，访问越界下标 $i>n$ 时，会得到 $a_i=0$。但是在一次程序运行过程中，如果访问越界下标超过 $k$ 次，程序就会崩溃。现在你需要求出有多少不同的 $n$（$n\in[l,r]$）可以让程序在不崩溃的情况下得到正确结果。

Input

第一行一个整数 $T$（$1\leq T\leq 10^3$），表示测试数据的组数。 接下来 $T$ 行，每行三个整数 $l,r,k$（$1\leq l\leq r\leq 10^{18},0\leq k\leq 10^{18}$），表示 $n$ 的范围和程序在不崩溃的情况下访问越界下标次数的上限。

Output

对于每组测试数据，输出一个整数，表示满足条件的不同的 $n$ 的个数。

Sample Input

3
1 100 0
1 100 1
1 100 2

Sample Output

7
28
61

Hint

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;
}
}

Source

2024“钉耙编程”中国大学生算法设计超级联赛（8）