← 返回题目列表

Codeforces · 2128/A

A. 回收中心

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

在回收中心,有$$$n$$$个垃圾袋,第$$$i$$$个垃圾袋的重量为$$$a_i$$$。每一秒,两个动作会连续发生:

  • 首先,您必须选择一个垃圾袋并将其销毁。如果垃圾袋的重量严格大于$$$c$$$,则需要​​花费$$$1$$$硬币,否则需要花费$$$0$$$硬币。
  • 然后,剩余每个垃圾袋的重量将乘以二。
要扔掉所有垃圾袋,您至少需要花费多少硬币?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$c$$$ ($$$1 \leq n \leq 30$$$, $$$1 \leq c \leq 10^9)$$$。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) - 每个垃圾袋的重量。

输出

对于每个测试用例,您必须输出一个整数 - 销毁所有垃圾袋所需花费的最小硬币数量。

示例

输入
复制

4
5 10
10 4 15 1 8
3 42
1000000000 1000000000 1000000000
10 30
29 25 2 12 15 42 14 6 16 9
10 1000000
1 1 1 1 1 1 1 1 1 864026633

输出
复制

2
3
6
1

注意

在下面的解释中:

  • 蓝色数字代表已免费销毁的垃圾袋,
  • 红色数字代表已销毁 $$$1$$$ 硬币的垃圾袋,
  • 黑色数字代表尚未销毁的垃圾袋。

在第一个测试用例中,一个解决方案是:

  • $$$[10, 4, 15, 1, 8]$$$
  • $$$[\color{blue}{10}, 8, 30, 2, 16]$$$,$$$10$$$ 被免费销毁,因为 $$$10 \leq 10$$$。
  • $$$[\color{blue}{10}, \color{blue}{8}, 60, 4, 32]$$$, $$$8$$$ 被免费销毁,因为 $$$8 \leq 10$$$。
  • $$$[\color{blue}{10}, \color{blue}{8}, 120, 8, \color{red}{32}]$$$, $$$32$$$ 被销毁为 $$$1$$$ 硬币,因为 $$$32 \gt 10$$$。
  • $$$[\color{blue}{10}, \color{blue}{8}, 240, \color{blue}{8}, \color{red}{32}]$$$, $$$8$$$ 被免费销毁,因为 $$$8 \leq 10$$$。
  • $$$[\color{blue}{10}, \color{blue}{8}, \color{red}{240}, \color{blue}{8}, \color{red}{32}]$$$, $$$240$$$ 被销毁为 $$$1$$$ 硬币,因为 $$$240 \gt 10$$$。

您总共支付了 $$$2$$$ 硬币,我们可以证明它是最优的。

在第二个测试用例中,一种解决方案是:

  • $$$[1\,000\,000\,000, 1\,000\,000\,000, 1\,000\,000\,000]$$$
  • $$$[\color{red}{1\,000\,000\,000}, 2\,000\,000\,000, 2\,000\,000\,000]$$$, $$$1\,000\,000\,000$$$ 被销毁为 $$$1$$$ 硬币,因为$$$1\,000\,000\,000 \gt 42$$$。
  • $$$[\color{red}{1\,000\,000\,000}, \color{red}{2\,000\,000\,000}, 4\,000\,000\,000]$$$, $$$2\,000\,000\,000$$$ 被销毁为 $$$1$$$ 硬币,因为$$$2\,000\,000\,000 \gt 42$$$。
  • $$$[\color{red}{1\,000\,000\,000}, \color{red}{2\,000\,000\,000}, \color{red}{4\,000\,000\,000}]$$$, $$$4\,000\,000\,000$$$ 被销毁$$$1$$$ 硬币,因为 $$$4\,000\,000\,000 \gt 42$$$。