Жадные алгоритмы

1) Больше всего у нас зеленых ягод (даже именно столько, сколько остальных в сумме). Поэтому давайте находить пары для зеленых. Всех зеленых можем соединить со всеми остальными цветами по парам. Получили вообще максимальное возможное количество разноцветных пар (50). Осталось проверить, что действительно все полученные пары разноцветные.

2) Давайте сначала оценим наименьшее возможное количество ходов:

. Теперь нужно попробовать добиться такого результата жадным алгоритмом. Давайте будем каждый раз брать по шарику из трех коробок с наибольшим количеством шариков. Получим:

(1, …, 7, 8, 9) -> (1, …, 6, 7, 8) -> (1, …, 6, 5, 6, 7) -> (1, …, 5, 5, 5, 5, 6) ->

(1, 2, 3, 4, 5, 5, 4, 4, 5) -> (1, 2, 3, 4, 4, 4, 4, 4, 4) -> (1, 2, 3, 3, 3, 3, 4, 4, 4) ->

(1, 2, 3, 3, 3, 3, 3, 3, 3) -> (1, 2, 2, 2, 2, 3, 3, 3, 3) -> (1, 2, 2, 2, 2, 2, 2, 2, 3) ->

(1, 1, 1, 2, 2, 2, 2, 2, 2) -> (1, 1, 1, 1, 1, 1, 2, 2, 2) -> (1, 1, 1, 1, 1, 1, 1, 1, 1) ->

(0, 0, 0, 1, 1, 1, 1, 1, 1) -> (0, 0, 0, 0, 0, 0, 1, 1, 1) -> (0, 0, 0, 0, 0, 0, 0, 0, 0)