P13160 [GCJ 2017 Qualification] Bathroom Stalls

某间洗手间有 $N + 2$ 个隔间排成一排，最左端和最右端的隔间被洗手间管理员永久占用。其余 $N$ 个隔间供用户使用。 每当有人进入洗手间时，他们会尽量选择距离其他人最远的隔间。为避免混淆，他们遵循如下确定性规则：对于每一个空隔间 $S$，计算两个值 $L_S$ 和 $R_S$，分别表示 $S$ 到其左侧最近被占用隔间之间的空隔间数，以及到其右侧最近被占用隔间之间的空隔间数。然后，他们会考虑那些最近邻距离最远的隔间，即使得 $\min(L_S, R_S)$ 最大的所有 $S$。如果只有一个这样的隔间，则选择它；否则，在这些隔间中选择 $\max(L_S, R_S)$ 最大的那个。如果仍有多个隔间并列，则选择这些隔间中最靠左的一个。 有 $K$ 个人即将依次进入洗手间；每个人都会在下一个人到来前选择好自己的隔间。没有人会离开。 当最后一个人选择隔间 $S$ 时，对于他所选隔间，$\max(L_S, R_S)$ 和 $\min(L_S, R_S)$ 的值分别是多少？

输入的第一行为测试用例数 $T$。接下来的 $T$ 行，每行描述一个测试用例，包含两个整数 $N$ 和 $K$，含义如上所述。

对于每个测试用例，输出一行，格式为 `Case #x: y z`，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为最后一个人选择的隔间 $S$ 的 $\max(L_S, R_S)$，$z$ 为 $\min(L_S, R_S)$。

**样例解释** 在样例 1 中，第一个人占据了中间两个隔间中最左边的一个，剩下的状态为（O 表示已占用，. 表示空）：`O.O..O`。然后，第二个人（也是最后一个人）占据了紧挨着右侧的隔间，此时一侧有 1 个空隔间，另一侧没有空隔间。 在样例 2 中，第一个人占据了中间的隔间，状态变为 `O..O..O`。然后，第二个人占据了最左边的隔间。 在样例 3 中，第一个人占据了两个中间隔间中最左边的一个，状态为 `O..O...O`。第二个人随后占据了连续三个空隔间中间的那个。 在样例 4 中，最后所有隔间都被占满，无论选择顺序如何。 在样例 5 中，唯一一个人选择了最左边的中间隔间。 **数据范围** - $1 \leq T \leq 100$。 - $1 \leq K \leq N$。 **小数据集 1（5 分，测试点 1 - 可见）** - $1 \leq N \leq 1000$。 **小数据集 2（10 分，测试点 2 - 可见）** - $1 \leq N \leq 10^{6}$。 **大数据集（15 分，测试点 3 - 隐藏）** - $1 \leq N \leq 10^{18}$。 由 ChatGPT 4.1 翻译