Colorful Balls#248

Colorful Balls (Editorial)

У кінці одна коробка має містити всі жовті м'ячики, інша — усі сині, третя — бути порожньою. Отже, розв'язок повністю визначається вибором: яка коробка стане «жовтою», а яка — «синьою». Третя автоматично лишається порожньою.

Порахуємо кількість переставлянь для фіксованого вибору. Нехай $S_{y}$ — загальна кількість жовтих м'ячиків, $S_{b}$ S_b — синіх. Якщо жовтою призначено коробку $i$ , то перекласти доведеться всі жовті м'ячики, які зараз не в ній, тобто $S_{y} - y_{i}$ S_y - y_i штук. Аналогічно, якщо синьою призначено коробку $j$ , перекласти треба $S_{b} - b_{j}$ S_b - b_j синіх м'ячиків.

Отже, вартість вибору дорівнює

(S_{y} - y_{i}) + (S_{b} - b_{j}), i \neq = j .

(S_y - y_i) + (S_b - b_j), \qquad i \ne j.

Упорядкованих пар різних коробок лише $3 \cdot 2 = 6$ 3 \cdot 2 = 6, тому просто переберемо всі й візьмемо мінімум. Рівносильно можна максимізувати $y_{i} + b_{j}$ y_i + b_j по $i \neq = j$ i \ne j.

Умова $i \neq = j$ i \ne j істотна: жовті та сині м'ячики не можуть опинитися в одній коробці. Випадки, коли якісь коробки порожні від початку, обробляються тією ж формулою без застережень.

S_{b}

S_{y} - y_{i}

S_{b} - b_{j}

(S_{y} - y_{i}) + (S_{b} - b_{j}), i \neq = j .

3 \cdot 2 = 6

y_{i} + b_{j}

i \neq = j

i \neq = j