Сегодня мы напишем два решения одной задачи с абсолютно разным подходом. Читаем условие:
В первом решении мы воссоздадим картину художника, выполняя те же действия, что и он. А именно, будем закрашивать прямоугольники = ставить нолики в каждую его клетку.
Первым делом считываем размеры полотна и создаём двумерный массив такого размера, заполнив его единичками (которые будут обозначать белый цвет):
Далее необходимо считать количество нарисованных прямоугольников и координаты каждого из них. Сделаем это в цикле:
Хранить все прямоугольники нам не надо, так как мы сразу будем их обрабатывать. А именно, пройдёмся по подмассиву, определяемому прямоугольником, и в каждый элемент поставим нолик, что будет обозначать закрашенную часть. Это делается очень просто с помощью двух вложенных циклов:
После этого осталось лишь посчитать количество единичек в массиве. А это равно сумме элементов. К сожалению, нельзя просто использовать встроенную функцию sum, поэтому сначала просуммируем каждую строку:
Худший случай для этого решения - когда каждый прямоугольник занимает весь холст. Тогда придётся выполнить 5,000 * 100 * 100 = 50,000,000 операций. Это очень много для Python, и решение не укладывается в лимит по времени. Однако, если выбрать PyPy, то, как это часто бывает, всё проходит.
Второе решение будет действовать в обратном порядке: для каждой точки будем проверять, а красит ли её хоть какой-нибудь прямоугольник.
Независимо от решения, всё равно сначала надо считать входные данные. Но теперь нам надо хранить все прямоугольники, так как к каждому придётся обращаться многократно:
Теперь заведём переменную для хранения ответа и предположим, что все точки непокрашены, то есть положим в неё w * h. И пройдёмся двумя вложенными циклами по всем точкам полотна:
Для каждой точки надо проверить каждый прямоугольник и убедиться, что она в неё не находится. А точнее, будем действовать наоборот: проверим, что точка красится прямоугольником, отнимаем от ответа единицу и заканчиваем цикл:
После проверки всех точек и всех прямоугольников, остаётся лишь вывести ответ:
И, на удивление, это решение укладывается в ограничения по времени на обычном Python даже без компиляции PyPy. Возможно, на сайте нет худшего теста для такого решения (когда все прямоугольники красят одну и ту же точку).
Предыдущий выпуск: Задача 85. Единичный НОД
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.