Есть у нас сколько-то фигурок. Известно, сколько из них какого цвета (N цветов) и сколько какой формы (M форм).
Как бы так найти минимальное количество сочетаний цвет-форма, на которые их все можно поделить?
Может это известная проблема и даже название есть?
так у тебя там не должно быть минимума. введи на множестве своих фигурок разноцветных отношение эквивалентности "фигурки эквивалентны, если у них одинаковая форма и цвет". очевидно, что это отн. эквивалентности и оно однозначно твоё множество разобьет на набор непересекающихся подмножеств. и ты хоть хуй соси, если хочешь рассказать человеку обо всем своём ассортименте фигурок, должен будешь перечислить все "имена" наборов.
первое известно, второе надо предложить, но так, чтоб кол-в групп было минимально.
>>35201
Нене, если сказано что 3 красных и 3 синих, 3 квадрата и 3 треугольника, могут быть 3 красных треугольника и 3 синих квадрата, а могут быть 3 красных квадрата и 3 синих треугольника.
На самом деле, как оказалась, эта задача в духе subset sum, нп-полная, как решать понятно.
В худшем случае N+M-1 групп, в лучшем max(n,m).
Я тебя нихуя не понял.
MxN - все комбинации цвет-форма.
Потом делим все имеющися фигурки на MN и получаем число фигурок каждой вариации, поровну.
Округляем до целых в одну из сторон, но конечная сумма всех должна совпасть с количеством фигурок.