Balls and Bins#347

Balls and Bins (Editorial)

Автор:

Тимкович Олександр

Підготували:

Тимкович Олександр

Розбір:

Тимкович Олександр

Давайте розглянемо кінцевий стан контейнерів. У кожному контейнері повинна бути однакова кількість кульок, нехай ця кількість це , тобто кінцевий стан це [x, x, x].

Зверніть увагу, що після того, як ми робимо одну операцію, то сумарна кількість кульок залишається такою самою. В кінцевому стані ми маємо [x, x, x], що означає, що наша загальна кількість кульок . А це означає, що a+b+c повинно ділитися на . Якщо це не так, то відповідь .

Також цікавий факт, що x=\frac{a+b+c}{3}, якщо відповідь існує.

Відповідь на задачу — це \frac{1}{2}(|x-a|+|x-b|+|x-c|). Потрібно зробити |x-a| операцій з першим контейнером (ми або переставляємо з контейнера в якийсь інший або доставляємо в нього). Такою самою ідеєю, ми отримуємо |x-b| та |x-c|. Також, не забувайте що однією операцією ми міняємо одразу два стани, тому це все потрібно розділити на .