小課題 3 (50 分)

给定一个整数 T，满足 0 ≤ T ≤ M，具体的值不知道。需要通过反复提问来确定 T 的值。

• 使用最少的提问次数来确定 T 的值。
• 如果连续 N 次的回答都是 "Yes"，则不能再继续提问。

实现过程中可以使用带有以下参数的函数 getT(N, M)：

• N：允许提问 "Yes" 的次数。
• M：T 的上限。

getT(N, M) 函数中可以重复调用 compare(X)。compare(X) 的规则如下：

• X：需要与 T 进行比较的整数，必须满足 0 ≤ X ≤ M。
• 返回值是一个整数，表示对于问题的回答是 "Yes"（即 X ≥ T 成立）还是 "No"（即 X < T 成立），分别为 1 和 0。

getT(N, M) 在反复提问的过程中需要确定隐藏的 T 的值，并将该 T 的值作为返回值返回。但如果在调用 compare(X) 时连续 N 次得到的返回值为 1，则之后不能再继续调用 compare(X)。

例子

例1

考虑 N = 1，M = 4 的情况。

在这种情况下，可以通过以下战略来确定 T 的值。假设调用 compare 的参数和返回值如下：

参数

返回值

compare(1)

0

compare(2)

0

compare(3)

1

根据 2 < T 和 3 ≥ T，可以确定 T = 3。因此，getT 函数应该返回 3。

例2

考虑 N = 2，M = 8 的情况。

在这种情况下，可以通过以下战略来确定 T 的值。假设调用 compare 的参数和返回值如下：

参数

返回值

compare(4)

1

compare(1)

0

compare(2)

0

compare(3)

1

根据 2 < T 和 3 ≥ T，可以确定 T = 3。因此，getT 函数应该返回 3。

小任务

小任务 1 (25 分)

• N = 1
• 1 ≤ M ≤ 100 000
• getT(N, M) 可以反复调用 compare(X)。

小任务 2 (25 分)

• N = 2
• 1 ≤ M ≤