← 返回题目列表

Codeforces · 1955/C

C. 深海的居民

中文机器翻译题面 查看原题

$$$n$$$ 船只出发探索海洋深处。船只编号从 $$$1$$$ 到 $$$n$$$,并按升序排列;第 $$$i$$$ 艘船的耐用性为 $$$a_i$$$。

Kraken 按照特定顺序攻击了船只 $$$k$$$ 次。首先,它攻击第一艘船,然后是最后一艘,然后再次攻击第一艘,依此类推。

海妖的每次攻击都会使飞船的耐久度降低 $$$1$$$。当船的耐久度下降到$$$0$$$时,它会沉没并且不再受到攻击(因此船不再是第一艘或最后一艘,海妖只攻击尚未沉没的船)。如果所有船只都沉没了,海妖就没有什么可攻击的了,它就会游走。

例如,如果 $$$n=4$$$、$$$k=5$$$ 和 $$$a=[1, 2, 4, 3]$$$,则会发生以下情况:

1.海妖攻击第一艘船,其耐久度为零,现在$$$a = [2, 4, 3]$$$;
2. Kraken 攻击最后一艘船,现在 $$$a = [2, 4, 2]$$$;
3. Kraken 攻击第一艘船,现在 $$$a = [1, 4, 2]$$$;
4. Kraken 攻击最后一艘船,现在 $$$a = [1, 4, 1]$$$;
5. Kraken 攻击第一艘船,其耐久度为零,现在 $$$a = [4, 1]$$$。

海妖袭击后击沉了多少艘船?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 10^{15}$$$) - 船只数量以及 Kraken 攻击船只的次数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 船舶的耐用性。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,在单独的行中输出 Kraken 击沉的船只数量。

示例

输入 #1

6
4 5
1 2 4 3
4 6
1 2 4 3
5 20
2 7 1 8 2
2 2
3 2
2 15
1 5
2 7
5 2

输出 #1

2
3
5
0
2
2