Всё очень просто.
-
Из входных данных сформируем два массива. Массив в котором хранится количество шаров для каждого цвета (под i-ым индексом лежит количество шаров i+1-ого цвета). И массив в котором хранится количество шаров для каждого контейнера (под i-ым индексом лежит количество шаров в i+1-ом контейнере).
-
Отсортируем их по возрастанию (по убыванию) и получим, что для каждого контейнера мы сопоставили цвет и наоборот.
-
Проверим, что сопоставленные в массивах значения равны.
Если это выполняется, то шары можно отсортировать. Иначе нет (не выполняется условие (4)).
Количество шаров в любом контейнере не изменяется при выполнении операции swap
- В каждом контейнере лежат лишь шары одинакового цвета
- Каждый цвет лежит лишь в одном контейнере
Из условия (1) следует, что каждому контейнеру соответствует цвет шара. Из условия (2) следует, что каждому цвету соответствует контейнеру.
Таким образом можно построить взаимно однозначное соответствие между цветом шара и контейнером. (3)
Из инварианта и (3) легко увидеть, что количество шаров одного цвета должно быть равно количеству шаров в соответствующем цвету контейнере. Или же для любого цвета существует контейнер количество шаров в котором равно количеству шаров выбранного цвета. (4)
Можно доказать, что при выполнении условия (4) мы всегда можем отсортировать шары так, чтобы выполнялись условия (1) и (2).
Доказывать будем по принципу математической индукции: где n - количество контейнеров, а m - количество шаров (m >= n)
Очевидно, что шары отсортированы.
Пусть шары в контейнерах лежат в перемешку (иначе шары отсортированы). Из условия (4) нам известно, что есть контейнер в котором лежат шары, количество которых равно количеству шаров (например) 1-ого цвета. В таком случае просто перемещаем в этот контейнер все шары 1-ого цвета. Очевидно, что это можно сделать. Шары отсортированы. База доказана
Мы можем отсортировать все m >= n шаров в n контейнерах.
Воспользуемся тем же действием, что и в базе индукции, просто перемещаем все шары 1-ого цвета в контейнер, количество шаров в котором, равно количеству шаров 1-ого цвета. Получаем, что шары 1-ого цвета отсортированы, осталось n цетов. По предположению индукции мы можем их отсортировать. Утверждение доказано.
Также, очевидно, что условие (4) всегда будет выполнятся в отсортированном контейнере.
Таким образом для того чтобы сказать, можно ли отсортировать шары в контейнерах, нужно проверить выполнение условия (4).