В каждой клетке доски 60×2 написано неотрицательное число. Костя выбрал несколько строк (но не все) и заменил все стоящие в них числа на нули. После этого он выбрал несколько столбов (но не все) и заменил все стоящие в них числа на нули.
Какое наименьшее суммарное количество строк и столбцов должен выбрать Костя, чтобы заведомо сумма чисел в таблице уменьшилась хотя бы в четыре раза?
Пусть дана таблица размером 60×60, в каждой клетке которой записано неотрицательное число. После действий Кости остаётся только подматрица, состоящая из тех клеток, которые оказались в строках и столбцах, не выбранных им для обнуления. Если обозначить через r число выбранных строк, а через c число выбранных столбцов, то размер оставшейся подматрицы равен (60 – r)×(60 – c). Результат изменений – сумма в таблице уменьшилась, так как все числа в выбранных строках и столбцах стали равны нулю.
Чтобы условие задачи («сумма чисел уменьшилась хотя бы в четыре раза») выполнялось для люб...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
