3217. 洗手间困境 (Easy)

单点时限: 2.0 sec

内存限制: 256 MB

一洗手间有 (N + 2) 个水槽。最左边的水槽和最右边的水槽正在维修中,所以不能使用。其他的水槽都是可以使用的。

当有人进来的时候,TA 会选择离别人最远的水槽。具体来说是这样的:对于每一个水槽 (S),可以计算两个值 (L_S) 和 (R_S),分别表示该水槽相对于左边和右边最近的被占用的水槽之间有多少个没有被占用的水槽。然后选择 (min(L_S, R_S)) 最大的水槽。如果有多个满足条件的选择,就选择 (max(L_S, R_S)) 最大的水槽。如果还是有多个水槽满足要求,那么就选择最左边的。

现在有 (K) 个人即将进入洗手间,他们依次选择一个水槽,并且永远不会离开。问当最后一个人进来的时候,(max(L_S, R_S)) 和 (min(L_S, R_S)) 分别是多少。

输入格式

输入第一行是一个整数 (T), (1 \leq T \leq 100)。

接下来 (T) 行,每行两个整数 (N) 和 (K),(1 \leq K \leq N \leq 10^6)。

输出格式

对于每组测试数据,输入一行 Case x: y z。x 表示测试数据编号(从 1 开始),y 和 z 分别表示最后一个人进入洗手间时的 (max(L_S, R_S)) 和 (min(L_S, R_S))。

样例

Input
5
4 2
5 2
6 2
1000 1000
1000 1
Output
Case 1: 1 0
Case 2: 1 0
Case 3: 1 1
Case 4: 0 0
Case 5: 500 499

提示

在 Case 1 中,第一个人进来以后,变成了 O.O..O( O 表示被占用)。然后第二个人占用右数第二个空位。

在 Case 4 中,最终所有的水槽都被占用了。

8 人解决,9 人已尝试。

8 份提交通过,共有 21 份提交。

5.8 EMB 奖励。

创建: 3 年,3 月前.

修改: 2 年,11 月前.

最后提交: 3 年,2 月前.

来源: GCJ 2017 QR

题目标签