F - Weed Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

高橋君と青木君の家の庭には草 1, 草 2, \ldots, 草 N の N 本の草が生えており、草 i の高さは A_i です。 高橋君と青木君は次の方法で庭の草抜きを行う事にしました。

  • まず、青木君が高々 K 本の草を選んで抜く。

  • その後、高橋君が次の操作を庭の草がすべて抜けるまで繰り返す。

    • 残っている草のうち高さが最大のものの高さを H とする。残っている草のうち、高さが \frac{H}{2} より高いものを一斉に抜く。

青木君は、高橋君の操作回数が最小となるようにした上で、自分の抜く本数を最小にしたいと考えています。 このときの高橋君の操作回数と青木君の抜く草の本数を求めてください。

制約

  • 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

例えば青木君が草 4 (高さ 9) を選んで抜いたとき、残りの草の中で最も高いものは草 3 であり、その高さは 4 です。 \frac{4}{2}=2 であり、2<3, 2<4 より 1 回目の操作で高橋君は草 2 と草 3 のみを抜くことができます。その後、 2 回目の操作で草 1 を抜き、高橋君は 2 回で操作を終えることができます。 一方で、青木君がどの草を 1 本選んだとしても高橋君は 1 回で操作を終えることはできません。

また、もし青木君が 1 本も抜かなかったとすると高橋君は 3 回操作する必要があるため、青木君は高橋君の操作回数を最小にするために最低 1 本は抜かなくてはなりません。

入力例 2

3 3
2 3 5

出力例 2

0 3

青木君が全ての草を抜いたとき高橋君は操作を行う必要がなく、明らかにこのときが最小です。

入力例 3

9 8
137 55 56 60 27 28 133 56 55

出力例 3

1 4

Score : 600 points

Problem Statement

Takahashi's and Aoki's garden is covered with N weeds, called Weed 1, Weed 2, \ldots, Weed N. The height of Weed i is A_i. Takahashi and Aoki have decided to pull these weeds, as follows:

  • First, Aoki will choose at most K weeds and pull them.
  • Then, Takahashi will repeat the following operation until all weeds are pulled.
    • Let H be the height of the tallest remaining weeds. Pull all weeds with heights above \frac{H}{2} at once.

Aoki wants to minimize the number of operations done by Takahashi. Also, he wants to minimize it by pulling the minimum number of weeds needed. Find the number of operations done by Takahashi and the number of weeds Aoki pulls in this case.

Constraints

  • 1 \leq N \leq 2\times 10^5
  • 0 \leq K \leq N
  • 1 \leq A_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \ldots A_N

Output

Print the number of operations Takahashi will do and the number of weeds Aoki will pull, in this order, with a space in between.

Sample Input 1

4 1
2 3 4 9

Sample Output 1

2 1

For example, assume that Aoki chooses Weed 4, with height 9, and pulls it. Then, the tallest remaining weed is Weed 3, with height 4. We have \frac{4}{2}=2, and Takahashi will pull Weed 2 and 3 in the first operation, since 2<3 and 2<4. Then, he will pull Weed 1 in the second operation, completing his work in two operations. On the other hand, he will not complete his work in one operation, no matter which one weed Aoki chooses.

Also, if Aoki pulls no weed, Takahashi will have to do three operations, so Aoki must pull at least one weed to minimize the number of operations done by Takahashi.

Sample Input 2

3 3
2 3 5

Sample Output 2

0 3

If Aoki pulls all weeds, Takahashi has to do zero operations, which is obviously the smallest number possible.

Sample Input 3

9 8
137 55 56 60 27 28 133 56 55

Sample Output 3

1 4