10,2 тыс подписчиков

🖥 Задача. Подготовка экспедиции на Марс

N кандидатов готовятся к двум космическим экспедициям на Марс. Поскольку экспедиции будут продолжаться несколько лет, а их участники окажутся в замкнутом пространстве небольшого объёма, то важное значение приобретает психологическая совместимость членов экипажа.

Путём тестирования были установлены пары кандидатов, присутствие которых в одной и той же экспедиции было бы нежелательным. Результаты тестирования отражены в таблице размера NxN. Если на пересечении -той строки и $j$-го столбца таблицы находится знак «+», то участие -го и $j$-го кандидатов в одной экспедиции нежелательно.

Составьте программу, разделяющую кандидатов на две группы для участия в экспедициях. Если такое разделение невозможно, программа должна выводить сообщение «No solution». В противном случае, программа должна выводить номера кандидатов, принадлежащих первой группе. Первой группой мы будем считать группу, в которой меньше кандидатов.

Естественно, хорошо написанная программа должна стремиться к тому, чтобы размеры групп не очень сильно отличались. Поэтому, если возможно несколько разбиений на группы, программа должна выбирать разбиение с минимальной разностью количеств кандидатов в группах. При этом в случае, если разбиений с минимальной разницей всё равно получается несколько, для определённости выбирается разбиение, в котором первая группа лексикографически меньше, чем первые группы остальных разбиений.

Программа должна считывать со стандартного потока ввода количество кандидатов и матрицу размера NxN. Например, для входных данных

- - + - - - - -

- - - + - - - -

+ - - - - - - +

- + - - - + - -

- - - - - - - -

- - - + - - - -

- - - - - - - +

- - + - - - + -

программа должна выводить

1 2 6 8

👉 Пишите ваше решение в комментариях👇

@machinelearning

1 минута

19 марта 2023

1122 читали