Задача «Стабильный коллектив»

Здесь приведён разбор задачи с Международной студенческой олимпиады по программированию (ACM ICPC 2006, четверть финала, МГУ, Москва). Эта задача была одной из сложных и интересных задач этой олимпиады. У неё достаточно простое решение, но догадаться до него самостоятельно не так просто. Попробуйте сами догадаться до метода решения, проследите за ходом своих мыслей и обратите внимание на ключевые шаги. Попробовать свои решения можно на сайте http://acm.mipt.ru/judge (задача 106).

Примечание: Предполагается, что читатель знаком с языком программирования C++ и стандартной библиотекой шаблонов STL.