← 返回题目列表

Codeforces · 1471/A

A. 奇怪的分区

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

给定一个长度为 $$$n$$$ 的数组 $$$a$$$ 和一个整数 $$$x$$$。您可以根据需要多次执行以下操作(可能为零):用数组的两个相邻元素的总和替换它们。例如,如果初始数组为 $$$[3, 6, 9]$$$,则在单个操作中,可以将最后两个元素替换为其总和,生成数组 $$$[3, 15]$$$,或者替换前两个元素以获取数组 $$$[9, 9]$$$。请注意,每次操作后数组的大小都会减小。

数组 $$$b=[b_1, \ldots, b_k]$$$ 的美妙之处被定义为 $$$\sum_{i=1}^k \left\lceil \frac{b_i}{x} \right\rceil$$$,这意味着我们将每个元素除以 $$$x$$$,将其四舍五入到最接近的整数,并对结果值求和。例如,如果 $$$x = 3$$$,且数组为 $$$[4, 11, 6]$$$,则数组的美度等于 $$$\left\lceil \frac{4}{3} \right\rceil + \left\lceil \frac{11}{3} \right\rceil + \left\lceil \frac{6}{3} \right\rceil = 2 + 4 + 2 = 8$$$。

请确定通过对原始数组执行一些操作可以获得的最小和最大美感。

输入

第一个输入行包含一个整数 $$$t$$$ — 测试用例的数量 ($$$1 \le t \le 1000$$$)。

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

下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$),数组 $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 值之和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出两个整数——最小和最大可能的美感。

示例

输入 #1

2
3 3
3 6 9
3 3
6 4 11

输出 #1

6 6
7 8

注意

在第一个测试用例中,如果我们执行任何操作,数组的美丽不会改变。

在第二个示例中,我们可以保持数组不变以获得最大的美观度,而为了获得最小的美观度,可以将两个元素 $$$4$$$ 和 $$$11$$$ 替换为它们的总和,生成一个数组 $$$[6, 15]$$$,其美观度等于 $$$7$$$。