First, we show that the maximum number of operations is \(\lfloor\log_2 (\max(A_i))\rfloor+1\), no matter how many number of weeds Aoki pulls, under the constraint in the problem. (Here, \(\lfloor x \rfloor\) denotes a maximum integer not exceeding \(x\).) This is true because after a operation the heights of remaining weeds are no more than those before the operation. Since \(A_i<2^{\lfloor\log_2 (\max(A_i))\rfloor+1}\), if the weeds still remain after the \(\lfloor\log_2 (\max(A_i))\rfloor\)-th operation, their heights is less than \(2\), so the heights are all \(1\). Therefore, the \(\lfloor\log_2 (\max(A_i))\rfloor+1\) is the final operation.

Now, let us consider solving this problem with a DP (Dynamic Programming). We first sort the heights of weeds in the increasing order. That is, we assume \(A_1\leq A_2\leq\cdots \leq A_N\).

Let

\(dp[i][j]={}\)(given the first \(i\) weeds, the minimum number of weeds to pull required for Aoki to finish in at most \(j\) operations),

and consider finding this value. Here, due to the fact shown above and \(\lfloor\log_2 (10^9)\rfloor+1=30\), we only have to consider \(j\) within the range \(0\leq j\leq 30\).
Next, we will consider the initial value and the transitions. First, when \(i=0\), there are no weeds, so \(dp[0][j]=0\). For \(i\geq 1\), by definition \(dp[i][0]=i\), and for each \(j\geq 1\), the minimum value if Aoki pulls the weed \(i\) is \(dp[i-1][j]+1\). On the other hand, if Aoki did not pull the weed \(i\), then the highest weed remaining before the first operation is \(A_i\), so it is \(dp[f(i)][j-1]\), where \(f(i)\) is defined as the largest index of weed with the height less than or equal to \(\frac{A_i}{2}\) (or \(f(i)=0\) if \(\frac{A_i}{2}<A_1\)). Therefore, \(dp[i][j]=\min(dp[i-1][j]+1,dp[f(i)][j-1])\).

All that left is computing \(f(i)\). By the definition, \(f(i)\leq f(i+1)\), so \(f(i+1)\) can be defined as \(j\) that is initialized with \(j=f(i)\) and repeatedly incremented as long as \(\frac{A_i}{2}<A_{j+1}\). Therefore, by repeating this, they can be computed in a total of \(O(N)\) time. Also, for each \(i\) we can apply binary search in an \(O(\log N)\) time, so that it finishes in a total of \(O(N\log N)\). This is still fast enough.

Back to the original problem, the minimum \(j\) such that \(dp[n][j]\leq K\) is the minimum number of operations required for Takahashi, and \(dp[n][j]\) here is the minimum number of weeds Aoki has to pull. Now we have all we want.

In the DP, each transition can be done in an \(O(1)\) time, so the entire DP finishes in \(O(N\log (\max(A_i)))\) time, Therefore, the problem has been solved fast enough.

Sample code in C++:

#include <bits/stdc++.h>

using namespace std;

#define N 200010
#define rep(i, n) for(int i = 0; i < n; ++i)

int main(void) {
	int n, k;
	int a[N];
	int dp[N][31];
	int b[N];
	cin >> n >> k;
	rep(i, n)cin >> a[i];
	sort(a, a + n);
	int cur = 0;
	rep(i, n) {
		while (a[cur] <= (a[i] / 2))cur++;
		b[i] = cur;
	}
	rep(j, 31)dp[0][j] = 0;
	rep(i, n) {
		dp[i + 1][0] = dp[i][0] + 1;
		rep(j, 30) {
			dp[i + 1][j + 1] = min(dp[i][j + 1] + 1, dp[b[i]][j]);
		}
	}
	rep(j, 31) {
		if (dp[n][j] <= k) {
			cout << j << " " << dp[n][j] << endl;
			return 0;
		}
	}
	return 0;
}