Problem A: Maximizing Happiness on the Bus
The key to maximizing happiness is to seat family members together as much as possible. If two members of the same family sit in the same row, both will be happy, and we only use two seats. However, if they are seated separately, only one person is happy, but two seats are still used. Therefore, we prioritize seating family pairs together first.
Once all possible pairs are seated, there may still be some family members left to seat. If a family has an odd number of members, one person will be left without a pair. Ideally, we want to seat this person alone in a row to make them happy. However, if there are no remaining rows to seat them alone, we’ll have to seat them with someone from another family. This means the other person might no longer be happy since they are no longer seated alone.
The easiest way to handle part 2 is to check the number of remaining rows and people. If the number of remaining rows is greater than or equal to the number of unpaired people, all unpaired people can sit alone and remain happy. Otherwise, some people will have to share a row, and their happiness will be affected. In that case, the number of unhappy people will be 2 × remaining rows - remaining people.
# Problem B: Kar Salesman
Since no customer can buy more than one car from the same model, the minimum number of clients we need is determined by the model with the most cars. Therefore, we need at least: [ \max(a_1, a_2, \dots, a_n) ] clients, because even if a customer buys cars from other models, they cannot exceed this limit for any single model.
Each client can buy up to x cars from different models. To distribute all the cars among the clients, we also need to consider the total number of cars. Thus, the minimum number of clients needed is at least: [ \left\lceil \frac{a_1 + a_2 + \dots + a_n}{x} \right\rceil ] This ensures that all cars can be distributed across the clients, respecting the limit of x cars per customer.
The actual number of clients required is the maximum of the two values: [ \text{min clients} = \max\left(\left\lceil \frac{a_1 + a_2 + \dots + a_n}{x} \right\rceil, \max(a_1, a_2, \dots, a_n)\right) ] This gives us a lower bound for the number of clients required, satisfying both constraints (the maximum cars from a single model and the total number of cars).
To demonstrate that this is always sufficient, we can reason that the most efficient strategy is to reduce the car count for the models with the largest numbers first. By doing so, we maximize the benefit of allowing each client to buy up to x cars from different models.
After distributing the cars, two possible outcomes will arise: 1. All models will have the same number of remaining cars, and this situation will be optimal when the total cars are evenly distributed (matching the \left\lceil \frac{a_1 + \dots + a_n}{x} \right\rceil bound). 2. A few models will have fewer than x cars remaining, which matches the case where the maximum number of cars from a single model (\max(a_1, \dots, a_n)) determines the bound.
Imagine a grid of size w × x, where w represents the minimum number of clients needed: [ w = \max\left(\left\lceil \frac{a_1 + a_2 + \dots + a_n}{x} \right\rceil, \max(a_1, a_2, \dots, a_n)\right) ] Now, place the cars in this grid by filling it column by column, from the first model to the n-th model. This method ensures that each client will buy cars from different models and no client exceeds the x car limit. Since the total number of cars is less than or equal to the size of the grid, this configuration guarantees that all cars will be sold within w clients.
