N кандидатов готовятся к двум космическим экспедициям на Марс. Поскольку экспедиции будут продолжаться несколько лет, а их участники окажутся в замкнутом пространстве небольшого объёма, то важное значение приобретает психологическая совместимость членов экипажа.
Путём тестирования были установлены пары кандидатов, присутствие которых в одной и той же экспедиции было бы нежелательным. Результаты тестирования отражены в таблице размера NxN. Если на пересечении -той строки и $j$-го столбца таблицы находится знак «+», то участие -го и $j$-го кандидатов в одной экспедиции нежелательно.
Составьте программу, разделяющую кандидатов на две группы для участия в экспедициях. Если такое разделение невозможно, программа должна выводить сообщение «No solution». В противном случае, программа должна выводить номера кандидатов, принадлежащих первой группе. Первой группой мы будем считать группу, в которой меньше кандидатов.
Естественно, хорошо написанная программа должна стремиться к тому, чтобы размеры групп не очень сильно отличались. Поэтому, если возможно несколько разбиений на группы, программа должна выбирать разбиение с минимальной разностью количеств кандидатов в группах. При этом в случае, если разбиений с минимальной разницей всё равно получается несколько, для определённости выбирается разбиение, в котором первая группа лексикографически меньше, чем первые группы остальных разбиений.
Программа должна считывать со стандартного потока ввода количество кандидатов и матрицу размера NxN. Например, для входных данных
8
- - + - - - - -
- - - + - - - -
+ - - - - - - +
- + - - - + - -
- - - - - - - -
- - - + - - - -
- - - - - - - +
- - + - - - + -
программа должна выводить
1 2 6 8👉 Пишите ваше решение в комментариях👇
@python_job_interview