eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Простая монотонность

Простая монотонность

Лимит времени 1 секунда
Лимит использования памяти 256 MiB

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

Входные данные

Два числа N и k (1N1000, 1K10) — количество векторов и размерность. Далее N строк по k+1 числу в каждой — булевый вектор и значение функции в нём. Все числа - 0 или 1. Все вектора различны.

Выходные данные

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

Пример

Входные данные #1
8 3
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0
Выходные данные #1
2
1 8 
Источник III Международная Летняя школа программирования 2012 г. Севастополь