A Prize No One Can Win#9878

A Prize No One Can Win (Editorial)

Sort the item prices in non-decreasing order. Suppose the offer includes items with prices $c_{1} \leq c_{2} \leq ... \leq c_{k}$ c_1 \le c_2 \le ... \le c_k. The best choice for a customer is to buy the two most expensive of them — $c_{k - 1}$ c_{k−1} and $c_{k}$ c_k. If $c_{k - 1} + c_{k} > x$ c_{k−1} + c_k > x, the customer receives a free unicorn horn.

Let $a_{1}, a_{2}, ..., a_{n}$ a_1, a_2, ..., a_n be the sorted prices of all $n$ items. Then the offer should include the items with prices $a_{1}, a_{2}, ..., a_{k}$ a_1, a_2, ..., a_k, where $k$ is the largest index such that $a_{k - 1} + a_{k} \leq x$ a_{k−1} + a_k \le x.

Example

In the first example, the sorted prices are ${1, 2, 3, 4, 5}$ \{1, 2, 3, 4, 5\}. Since $x = 6$ x = 6, we look for the largest index $k$ such that $a_{k - 1} + a_{k} \leq 6$ a_{k−1} + a_k \le 6. This is $k = 3$ k = 3, because $2 + 3 \leq 6$ 2 + 3 ≤ 6, but $3 + 4 > 6$ 3 + 4 > 6.

In the second example, the sorted prices are ${1, 4, 7, 8, 9}$ \{1, 4, 7, 8, 9\}. Since $x = 10$ x = 10, the largest index $k$ is $2$ : $1 + 4 \leq 10$ 1 + 4 \le 10, but $4 + 7 > 10$ 4 + 7 > 10.

Algorithm implementation

Read the input data.

scanf("%d %d", &n, &x);
v.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &v[i]);

Sort the item prices in non-decreasing order.

sort(v.begin(), v.end());

Iterate over pairs of adjacent items $i$ and $i + 1$ i + 1. As soon as $v_{i} + v_{i + 1} > x$ v_i + v_{i+1} > x, the item with price $v_{i + 1}$ v_{i+1} and all items after it can no longer be included in the offer.

res = n;
for (i = 0; i + 1 < n; i++)
  if (v[i] + v[i + 1] > x)
  {

Then the maximum number of items in the offer is $i + 1$ i + 1 (items are numbered from zero).

    res = i + 1;
    break;
  }

Print the answer.

printf("%d\n", res);