← 返回题目列表

AtCoder · abc203_f

F. 杂草

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

分数: 600 点

问题陈述

高桥和青木的花园里覆盖着 N 杂草,称为杂草 1, 杂草 2, \ldots, 杂草 N。杂草的高度 i is A_i。 高桥和青木决定拔掉这些杂草,具体如下:

  • 首先,青木最多会选择 K 杂草并拔掉它们。
  • 然后,高桥会重复下面的操作,直到所有的杂草都被拔掉。
    • 让 H 是剩余最高杂草的高度。拔除高度以上的所有杂草 立即 \frac{H}{2} 。

Aoki 希望尽量减少 Takahashi 执行的操作次数。此外,他还想通过拔除所需最少数量的杂草来最大程度地减少这种情况。 求此例中高桥进行的手术次数和青木拔除的杂草数量。

约束

  • 1 \leq N \leq 2\times 10^5
  • 0 \leq K \leq N
  • 1 \leq A_i \leq 10^9
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N K
A_1 A_2 \ldots A_N

输出

按顺序打印高桥将执行的操作数量和青木将拔除的杂草数量,中间有一个空格。


示例输入 1

4 1
2 3 4 9

示例输出 1

2 1

例如,假设 Aoki 选择 Weed 4,有高度 9,然后拉它。然后,剩下的最高的杂草是Weed 3,有高度 4。 我们有 \frac{4}{2}=2,高桥会拔除杂草 2 和 3 在第一次操作中,由于 2<3 和 2<4。然后,他会拔除杂草 1 在第二次手术中,分两次手术完成了他的工作。 另一方面,无论青木选择哪一种杂草,他都不会一次性完成工作。

另外,如果青木没有拔除杂草,高桥将需要进行 3 次操作,因此青木必须至少拔除一颗杂草,以尽量减少高桥进行的操作次数。


示例输入 2

3 3
2 3 5

示例输出 2

0 3

如果青木拔掉所有杂草,高桥就必须进行零运算,这显然是可能的最小数量。


示例输入 3

9 8
137 55 56 60 27 28 133 56 55

示例输出 3

1 4