← 返回题目列表

Codeforces · 1623/C

C. 平衡的石堆

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

有 $$$n$$$ 堆石头。第 $$$i$$$ 堆有 $$$h_i$$$ 石头。您想要通过执行以下过程一次来更改堆中石头的数量:

- 按此顺序从 $$$3$$$-rd 堆到 $$$n$$$-th 堆遍历堆。
- 令 $$$i$$$ 为当前堆的编号。
- 你可以选择一个数字 $$$d$$$ ($$$0 \le 3 \cdot d \le h_i$$$),将 $$$d$$$ 棋子从第 $$$i$$$ 堆移动到第 $$$(i - 1)$$$ 堆,并将 $$$2 \cdot d$$$ 棋子从第 $$$i$$$ 堆移动到第 $$$(i - 2)$$$ 个堆。
- 因此,$$$h_i$$$ 减少 $$$3 \cdot d$$$,$$$h_{i - 1}$$$ 增加 $$$d$$$,$$$h_{i - 2}$$$ 增加 $$$2 \cdot d$$$。
- 您可以为不同的操作选择不同或相同的$$$d$$$。有些堆可能会变空,但它们仍然算作堆。

处理后最小堆中的石子最大数量是多少?

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$h_1, h_2, h_3, \ldots, h_n$$$ ($$$1 \le h_i \le 10^9$$$)。

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

输出

对于每个测试用例,打印最小堆可以包含的最大石头数。

示例

输入 #1

4
4
1 2 10 100
4
100 100 100 1
5
5 1 1 1 8
6
1 2 3 4 5 6

输出 #1

7
1
1
3

注意

在第一个测试用例中,初始堆大小为 $$$[1, 2, 10, 100]$$$。我们可以按如下方式移动石头。

- 将 $$$3$$$ 石子和 $$$6$$$ 从 $$$3$$$-rd 堆分别移动到 $$$2$$$-nd 和 $$$1$$$ 堆。堆大小将为 $$$[7, 5, 1, 100]$$$;
- 将 $$$6$$$ 石子和 $$$12$$$ 石子从最后一个堆分别移动到 $$$3$$$-rd 和 $$$2$$$-nd 堆。堆大小将为 $$$[7, 17, 7, 82]$$$。

在第二个测试用例中,最后一个堆是 $$$1$$$,我们无法增加其大小。

在第三个测试用例中,最好不要移动任何石头。

在最后一个测试用例中,最终可实现的堆配置可以是 $$$[3, 5, 3, 4, 3, 3]$$$。