Fruits

Key observation

The actual fruit names are mostly noise. We only need to know how many times each distinct fruit appears in Valera's list.

If some fruit appears $c$ times and Ashot assigns it price $p$, then that fruit contributes

$$c \cdot p$$

to the total cost.

So after counting the list, the problem becomes:

Given frequencies $freq_1, freq_2, \dots, freq_d$ and $n$ price tags, assign one price to each of these $d$ fruits to minimize or maximize

$$\sum_{i=1}^{d} freq_i \cdot price_i.$$

Here $d$ is the number of distinct fruits in the list, and the statement guarantees $d \le n$.

Which price tags matter?

For the minimum, every frequency is positive, so assigning a larger price instead of a smaller unused one can only make the sum worse. Therefore, the minimum uses the cheapest $d$ price tags.

For the maximum, similarly, it uses the most expensive $d$ price tags. The unused tags can be slapped onto fruits Valera does not buy. Ashot can do that; nobody cares.

How to pair them?

For minimization, big frequencies should get small prices.

Suppose $a \ge b$ are two frequencies and $x \le y$ are two prices. Compare the two pairings:

$$a \cdot x + b \cdot y$$

versus

$$a \cdot y + b \cdot x.$$

Their difference is

$$(a \cdot x + b \cdot y) - (a \cdot y + b \cdot x) = (a-b)(x-y) \le 0.$$

So pairing the larger frequency with the smaller price is never worse. That proves the greedy pairing.

For maximization, flip the logic: pair large frequencies with large prices.

Algorithm

1. Read prices.
2. Count occurrences of each fruit name using a map.
3. Store all frequencies in a vector.
4. Sort frequencies in decreasing order.
5. Sort prices in increasing order.
6. Let $d$ be the number of distinct fruits.
   • Minimum: pair $freq_i$ with price[i].
   • Maximum: pair $freq_i$ with price[n - 1 - i].

Formally:

$$mn = \sum_{i=0}^{d-1} freq_i \cdot price_i$$ $$mx = \sum_{i=0}^{d-1} freq_i \cdot price_{n-1-i}$$

Complexity

Sorting dominates:

$$O(n \log n + d \log d)$$

with $d \le m \le 100$, so this is hilariously fast. Memory usage is

$$O(n + d).$$