День іменинника#127

День іменинника (Розбір)

Ключове спостереження: набори іменинників мають бути однаковими, тому типи шоколадок ніяк не змішуються між собою — кожен тип можна розглядати окремо.

Нехай шоколадок типу є штук. Щоб кожен із іменинників отримав однакову кількість шоколадок цього типу, ця кількість може бути будь-яким числом від до \lfloor \mathrm{cnt}[v] / K \rfloor. Оскільки ми максимізуємо загальну кількість, беремо максимум, тобто \lfloor \mathrm{cnt}[v] / K \rfloor штук типу на людину.

Отже, розв'язок такий:

  • одним проходом порахуємо для кожного типу; типів не більше , тому вистачить простого масиву-лічильника;

  • для кожного типу від до додамо до відповіді \lfloor \mathrm{cnt}[v]/K \rfloor і випишемо число саме стільки разів.

У першому рядку виводимо — сумарну кількість шоколадок на одну людину, у другому — самі типи. Оскільки ми перебираємо типи за зростанням, послідовність автоматично виходить неспадною, як і вимагає умова.

Складність — \mathcal{O}(N + 100), чого з великим запасом вистачає при N \le 10^5. Не забудьте про випадок M = 0: тоді другий рядок просто порожній.