06/04/2025 18:15:23

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2836. Поле Страшилы

Ограничения: время – 1500ms/3000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

До появления Элли в стране жевунов Страшила жил посреди большого прямоугольного поля и пугал ворон. Поле Страшилы состоит из одинаковых квадратных участков и имеет размеры $N xx M$ . На каждом участке выращивается $с_{ij}$ сельскохозяйственных культур по принципу севооборота: первая культура выращивается в первый год, вторая - во второй, …, $c_{ij}$ -я культура - в $c_{ij}$ -ый, а в $(c_{ij}+1)$ -ый год участок пустует для восстановления плодородия, затем всё повторяется: первая культура - $(c_{ij}+2)$ -ый год и так далее. Некоторые участки не возделываются ( $c_{ij}=0$ ).

Кроме фермерства, жевуны очень любят праздники. Для каждого из праздников они занимают подходящий (для каждого праздника - свой) прямоугольный кусок поля и ставят на нем шатры и аттракционы. Но чтобы не терять урожай, все занятые под празднование участки должны в соответствующий год пустовать. Определите, как скоро жевуны смогут провести каждый из праздников.

В первой строке ввода указаны три натуральных числа: $N$ и $M$ - размеры поля ( $1<=N,M <= 200$ ), $Q$ - количество праздников ( $Q <= 10^6$ ). Затем следует $N$ строк по $M$ чисел в каждой - схема поля. Каждый участок описывается одним целым числом $c_{ij}$ ( $0<=c_{ij}<=40$ ) - количеством культур, выращиваемых на нем. Затем следует $Q$ строк по 4 целых числа в каждой - описания частей поля, необходимых для проведения каждого из праздников: $i_1, j_1$ - координаты поля, находящегося в верхнем левом углу нужной территории, $i_2, j_2$ - координаты поля в правом нижнем углу ( $1<=i_1<=i_2<=N$ , $1<=j_1<=j_2<=M$ ).

Выведите $Q$ натуральных чисел, по одному для каждого из праздников: минимальный номер года, в который все соответствующие участки будут свободны.

Пример ввода

Пример вывода

1
2
12

Пояснение к примеру.
В первом случае, оба требуемых участка всегда пустуют и их можно занять в первый же год.
Во втором случае, единственный возделываемый участок (1,5) будет занят в первый год и освободится во второй.
В третьем случае, в каждый из первых 11 лет хотя бы один из участков поля будет занят. На 12 год все участки освободятся.

29/03/2025	Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 9)
29/03/2025	ЦОП: дорешивание Prime Time 2025 (проводит BOGAT) (K)