orchard. in | |
Имя выходного файла: | orchard. out |
Максимальное время работы на одном тесте: | 4 секунды |
Максимальный объем используемой памяти: | 12 мегабайт |
Максимальная оценка за задачу: | 120 баллов |
Давным-давно в тридевятом королевстве жил-был король. В честь его рождения была посажена первая (самая древняя) яблоня. После этого вокруг нее в честь других событий высаживались еще яблони на расстоянии 1 метр друг от друга строго по направлению на юг, на север, на запад или на восток. В результате чего все яблони оказались на пересечении рядов, идущих с юга на север и с запада на восток. Другими словами, все яблони оказались в узлах прямоугольной сетки с шагом 1 метр.
Много воды утекло с тех пор – некоторые яблони погибли в сезоны больших засух, некоторые не смогли пережить периоды наводнений. Могла погибнуть и самая древняя яблоня. Задался новый король вопросом – а сколько же яблонь растет в его саду? Для этого он поручил своему главному советнику пересчитать их. Нелегкая работа досталась советнику – ведь сад был огромный.
Поэтому советник сначала решил перенумеровать ряды яблонь. Отсчет он начал с места, где была посажена самая древняя яблоня. Направление на север и восток он решил считать положительным, а направление на запад и юг отрицательным. Таким образом, ряды, расположенные севернее и восточнее самой древней яблони нумеруются положительными числами (1, 2, … ), а ряды, расположенные южнее и западнее самой древней яблони нумеруются отрицательными числами (-1, -2, …). Положение самой древней яблони - (0,0).
(рисунок 1)
Яблони обозначены серыми кружками, самая древняя яблоня – черным.
Разобравшись с нумерацией, советник приступил непосредственно к измерениям. Выбрав две какие-либо яблони, он соединял их веревочкой. Соединение получалось удачным, если при прохождении веревочки через точки пересечения перпендикулярных рядов во всех них оказывалось по яблоне. Удачное соединение он считал «правильным яблоневым отрезком». Отрезок, начало и конец которого совпадают, советник также считал «правильным яблоневым отрезком». Такой отрезок содержал в себе одну яблоню.
Советник находил и записывал некоторые «правильные яблоневые отрезки» и в результате своей многодневной работы советник получил список таких отрезков. Кроме того, советник утверждал, что нет ни одной яблони, которая не была бы включена в какой-либо «правильный яблоневый отрезок», записанный в его список.
Но возникла новая проблема, о которой советник не подумал вначале. Действительно, некоторые яблони могли быть посчитаны несколько раз: «правильные яблоневые отрезки» могли пересекаться, перекрываться и даже быть вложенными друг в друга. Поэтому не так то просто получить общее количество яблонь по списку советника.
Напишите программу, которая по записям советника находит количество яблонь, которые растут в саду.
Формат входных данных
В первой строке входного файла дано количество записей советника K (0 <= K <= 103).
Далее идут K строк с описаниями правильных яблоневых отрезков по одному описанию в строке.
Каждое описание состоит из четырех целых чисел (по модулю не превышающих 2*109) – координат начала и конца «правильного яблоневого отрезка», разделенных пробелом. Координаты – это номер ряда, идущего с юга на север, и номер ряда, идущего с запада на восток (в соответствии с нумерацией советника), на пересечении которых находится яблоня (см. рисунок 1).
Формат выходных данных
В выходной файл следует записать количество яблонь, которые растут в саду.
Примеры
(последний пример соответствует рисунку 1)
orchard. in | orchard. out |
3 1 1 1000 1 1 2 1000 2 1 3 1000 3 | 3000 |
2 -1 0 1 0 0 -1 0 1 | 5 |
3 -2 -2 2 2 1 1 3 3 -2 1 2 -1 | 8 |
Большой, белый, прямоугольный
Входной файл: INPUT. TXT
Выходной файл: OUTPUT. TXT
Ограничение времени: 5 секунд на тест
В прямоугольной таблице клетки раскрашены в белый и черный цвета. Найти в ней прямоугольную область белого цвета, состоящую из наибольшего количества ячеек.
Входные данные
Во входном файле записана сначала высота N, а затем ширина M таблицы (1?N?100, 1?M?100), а затем записано N строк по M чисел в каждой строке, где 0 означает, что соответствующая клетка таблицы выкрашена в белый цвет, а 1 - что в черный.
Выходные данные
В выходной файл вывести одно число - количество клеток, содержащихся в наибольшем по площади белом прямоугольнике.
Пример входного и выходного файлов
INPUT. TXT
5 6
1 0 0 0 1 0
0 0 0 0 1 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0
OUTPUT. TXT
9
Расстановка скобок
Исходные данные - строка (не более 254 символов) из круглых скобок и знаков вопроса. Данные корректны. Составьте программу, печатающую все правильные скобочные выражения, которые можно восстановить из входной строки заменой знаков вопроса на скобки, либо сообщающую, что решения нет.
Пример 1. Исходная строка: ((??)?
Вывод программы: ((()))
(()())
Пример 2. Исходная строка: )?
Вывод программы: восстановить невозможно.
Известная геометрическая задачаИмя входного файла: | geometr. in |
Имя выходного файла: | geometr. out |
Максимальное время работы на одном тесте: | 1 секунда |
Максимальный объем используемой памяти: | 64 мегабайта |
Максимальная оценка за задачу: | 90 баллов |
В геометрии при изучении теоремы Пифагора часто встречается следующая задача.
Получить отрезок, длина которого точно равна 
, где N – целое число. Разрешается пользоваться бесконечной линейкой с нанесенными на нее делениями (цена деления равна 1) и угольником для получения прямых углов.
Построением считается процесс откладывания с помощью линейки одного отрезка любой длины кратной цене деления.
Например, для получения отрезка длины
достаточно построить два отрезка по 1 (2 построения),
а для получения отрезка, равного 
, можно построить отрезок, равный 2, и отрезок, равный 1, (2 построения) или получить отрезок, равный 
(2 построения), и отрезок, равный 1 (всего 3 построения).
Требуется написать программу, которая определяет минимальное количество построений, которые необходимо произвести, чтобы получить отрезок, длина которого точно равна 
, если это возможно.
Формат входных данных
Входной файл содержит единственное целое число N (N≤231) – квадрат длины отрезка, который надо получить.
Формат выходных данных
Первая строка должна содержать число K – количество построений, вторая строка должна содержать K чисел, разделенных пробелами, – длин отрезков, которые необходимо построить для получения отрезка заданной длины. Если какие либо отрезки используются в построении несколько раз – они указываются столько же раз.
Если построить невозможно, то вывести в выходной файл число 0.
Примеры
geometr. in | geometr. out |
4 | 1 2 |
2 | 2 1 1 |
6 | 3 2 1 1 |
