Задача №111909. Гости
Есть N человек, которые для простоты пронумерованы от 1 до N . Для каждых двух известно, знают ли они друг друга (если A знает B , то B знает A ). Мы хотим пригласить на званный вечер как можно больше человек, удовлетворяющих следующим двум условиям:
- Для каждого гостя должно быть хотя бы K знакомых ему людей
- Для каждого гостя должно быть хотя бы K незнакомых ему людей
Первая строка входного файла содержит два числа N и K (1 ≤ K < N ≤ 1000) . Каждая из следующих N строк содержит N целых чисел, каждое из которых либо ноль либо единица: j -ое число входной строки с номером i + 1 означает, знает ли человек i человека j ( 1 – знает, 0 – не знает). i -ое число входной строки с номером i + 1 всегда 0 .
Выведите в первой строке максимальное число гостей званного вечера, удовлетворяющих заданным условиям, и во второй строке их номера (в любом порядке).
2 1 0 1 1 0
0
3 1 0 1 0 1 0 1 0 1 0
0
4 1 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0
4 1 2 3 4