Переїзд#241

Переїзд (Розбір)

Речей лише чотири, а варіантів дії — п'ять, тому задача розв'язується повним перебором.

Спочатку порахуємо ваги коробок $S_{1}$ і $S_{2}$ S_2, просумувавши $w_{i}$ w_i за відповідними $t_{i}$ t_i. Поточне значення цільової функції — це $max (S_{1}, S_{2})$ \max(S_1, S_2).

Тепер розглянемо кожну з чотирьох речей і подивимось, що станеться, якщо перекласти саме її. Якщо річ $i$ лежить у першій коробці, то після перекладання ваги стануть $S_{1} - w_{i}$ S_1 - w_i та $S_{2} + w_{i}$ S_2 + w_i, а нове значення — $max (S_{1} - w_{i}, S_{2} + w_{i})$ \max(S_1 - w_i,\; S_2 + w_i). Симетрично для речі з другої коробки.

Обираємо варіант з найменшим значенням $max$ . Якщо жодне перекладання не покращує початкове $max (S_{1}, S_{2})$ \max(S_1, S_2), виводимо $- 1$ ; інакше — номер речі (нумерація з одиниці).

Головне тут — не забути про варіант «нічого не робити»: він теж допустимий, і саме тому порівнювати нові значення треба з початковим, а не лише між собою. Якщо оптимальних перекладань кілька, підійде будь-яке.

Ваги сягають $1 0^{6}$ 10^6, а речей чотири, тому всі суми з запасом вміщуються у 32-бітний тип.

S_{2}

w_{i}

t_{i}

max (S_{1}, S_{2})

S_{1} - w_{i}

S_{2} + w_{i}

max (S_{1} - w_{i}, S_{2} + w_{i})

max (S_{1}, S_{2})

1 0^{6}