Ctrl K

Столбцы, закрывающие строки

Средняя
Дана таблица grid из нулей и единиц и число picks. Нужно отметить ровно picks различных столбцов. Строка считается закрытой, если каждая единица в ней стоит в одном из отмеченных столбцов. Строка без единиц закрыта всегда. Верните наибольшее число строк, которое можно закрыть, отметив picks столбцов.
Пример 1
grid=[[1, 0, 0], [0, 1, 0], [1, 1, 0], [0, 0, 0]], picks=1 → 2

Если отметить столбец 0, закрыты строки 0 и 3 (в строке 3 единиц нет вовсе). Столбец 1 тоже закрывает две строки, столбец 2 — только строку 3. Больше двух строк одним столбцом не закрыть.

Пример 2
grid=[[0, 1], [1, 1], [1, 0]], picks=2 → 3

Отмечены оба столбца, значит, закрыта каждая строка — ответ 3.

Ограничения
  • 1 ≤ grid.length ≤ 12
  • 1 ≤ grid[i].length ≤ 12, все строки одной длины
  • grid[i][j] равно 0 или 1
  • 1 ≤ picks ≤ grid[0].length
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиНаборы с полным OR СредняяПерестрелять соперника СредняяСамая сильная команда СредняяПереезды между офисами СложнаяXOR каждого подмножества Лёгкая
загружаем Python…
Вход
grid=[[1, 0, 0], [0, 1, 0], [1, 1, 0], [0, 0, 0]], picks=1
Ожидается
2

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 101 тест на сервере, включая скрытые.