--->
118 задач
<---
Источники
Известный художник решил написать новый шедевр. После многих дней усердной работы он захотел исследовать свое творение. Художник вспомнил, что картина писалась следующим образом. Сначала был взят белый холст, имеющий форму прямоугольника шириной w и высотой h. Затем художник нарисовал на этом холсте n прямоугольников с координатами углов (x1i;y1i), (x1i;y2i), (x2i;y2i), (x2i;y1i).
Помогите художнику определить площадь незакрашенной части холста.
Первая строка содержит два целых числа w и h (1 ≤ w;h ≤ 100) — ширину и высоту холста соответственно. Вторая строка входного файла содержит целое число n (0 ≤ n ≤ 5000) — количество прямоугольников. Следующие n строк содержат информацию о прямоугольниках. (i + 2)-ая строка содержит четыре целых числа x1i; y1i, x2i; y2i (0 ≤ x1i ≤ x2i ≤ w, 0 ≤ y1i ≤ y2i ≤ h).
Выведите ответ на задачу.
5 5 2 1 1 3 3 2 2 4 4
18
6 7 3 0 0 5 5 1 1 4 4 2 2 3 3
17
Дан двумерный массив целых чисел n × m, все элементы которого — нули или единицы. Найти в нём наибольший по площади квадрат, состоящий только из единиц. Гарантируется, что в нём есть хотя бы одна единица.
Вводятся два целых числа n и m (1 ≤ n, m ≤ 1000), а потом n строк по m чисел 0 или 1 — элементы массива.
Вывести три числа — длину стороны квадрата и координаты его левого верхнего угла.
1 1 1
1 1 1
3 5 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1
2 1 1
Имеется 4-мерный массив X, каждый индекс которого может принимать значения от 1 до N. Вы должны построить новый 4-мерный массив Y , элементы которого должны принимать следующие значения: \(Y\) [\(i_1\), \(i_2\), \(i_3\), \(i_4\)] = min(\(X\)[\(j_1\), \(j_2\), \(j_3\), \(j_4\)]), где 1 \(\le\) \(i_k\) \(\le\) \(N\) − \(M\) + 1, \(i_k\) \(\le\) \(j_k\) \(\le\) \(i_k\) + \(M\) − 1, а \(M\) - заданное число.
В первой строке входного файла задаются \(N\) и \(M\) (\(1\) \(\le\) \(M\) \(\le\) \(N\)). Остальные строки файла содержат элементы массива \(X\). Количество элементов не будет превышать 1500000 и сами они будут целыми числами, не превышающими по абсолютному значению \(10^9\). Они расположены в таком порядке, что считать их можно с помощью псевдокода:
for i = 1 to N:Выведите искомый массив \(Y\) в том же формате, в котором был дан массив \(X\).
1 1 1
1
3 2 3 1 4 -4 0 4 0 0 -3 0 -2 -5 5 3 5 -4 4 -3 -5 -4 -4 5 -1 0 -3 -2 -1 2 -5 -5 -1 1 1 -4 3 5 3 -3 -3 3 0 1 4 -1 -2 3 -2 5 4 -1 -5 3 -4 0 -3 -1 3 -1 4 4 -1 -5 -3 4 -4 5 1 5 -4 3 2 2 -2 -2 4 2 -4 -3 1 3 1
-5 -5 -4 -3 -5 -5 -4 -5 -5 -5 -5 -5 -4 -5 -4 -5
Рано утром Вася решил сделать домашнее задание по информатике. Начать выполнение задания Вася решил с поиска подходящей тетрадки. Добравшись до ящика с чистыми тетрадями, он открыл одну из них. Вася ещё не до конца проснулся и поэтому видит только часть тетрадки и не может сообразить, какая это тетрадка: в клетку, в линейку или в вертикальную линейку. Помогите ему это сделать.
Формально, дана двухмерная таблица из нулей и единиц — часть тетрадки, которую видит Вася. Единицей обозначается закрашенный участок, а нулем — незакрашенный. Назовём вертикальной линией столбец таблицы, все элементы которого — единицы, а горизонтальной линией — строку таблицы, все элементы которой — единицы. Гарантируется, что каждая единица в таблице содержится в какой-либо линии.
Тетрадкой в клетку называется тетрадка, в которой содержатся вертикальные и горизонтальные линии. Тетрадкой в линейку называется тетрадка, в которой содержатся только горизонтальные линии. Тетрадкой в вертикальную линейку называется тетрадка, в которой содержатся только вертикальные линии.
Известно, что в целой тетрадке все расстояния между линиями одинаковы (то есть все клетки — квадраты, все линейки одинаковой ширины). Гарантируется, что линии не могут располагаться рядом (между ними всегда есть промежуток).
Вам требуется написать программу, которая определит тип тетрадки или скажет, что это невозможно однозначно сделать по данной таблице.
В первой строке входных данных даны целые числа n и m (1 ≤ n, m ≤ 1 000) — количество строк и столбцов в таблице. Следующие n строк по m чисел содержат целые числа ai, j (0 ≤ ai, j ≤ 1) — элементы таблицы, задающие видимую часть тетради.
Требуется вывести одну из строк:
3 5
00100
11111
00100
Square
4 5
11111
00000
11111
00000
Line
5 5
00000
00000
11111
00000
00000
?
В данной задаче баллы за каждый тест начисляются независимо от прохождения остальных тестов и суммируются.
Однажды на уроке биологии Петя решил заполнить таблицу n × m числами от 1 до mn по строкам (пример заполнения для n = 3 , m = 4 показан на рисунке). Когда он закончил свой труд, его сосед Коля заинтересовался, можно ли по числу X определить, записано оно на краю таблицы или нет. Помогите Коле.
Под фразой "на краю" имеется в виду, что число X стоит в первом столбце или в первой строке или в последнем столбце или в последней строке.
В первой строке даны два целых числа n и m ( n , m ≤ 20 ). Во второй строке дано одно целое число X ( 1 ≤ X ≤ nm ).
Выведите YES, если число стоит на краю таблицы и NO в противном случае.
3 4 8
YES
3 4 6
NO