Каталог по темам

Задачи

Страница: 1 [Всего задач: 3]

Задача 98852

[Скалы ]

Тема:

[

Куча

]

Сложность: 4

На планете Олимпия рабочие строят новую дамбу. Часть плоскости, на которой проводятся строительные работы, имеет вид прямоугольника размером 1 x L метров, на котором введены координаты, как показано на рисунке.

Для поднятия ландшафта используют специально разработанные магические импульсаторы. Если магический импульсатор силой H поставить в точку с X-координатой p, то в каждой точке q отрезка [p-H;p] на оси X рельеф поднимается на q-p+H метров по всей его ширине (то есть для произвольного Z от 0 до 1), а в каждой точке q отрезка [p;p+H] рельеф поднимается на H+p-q метров по всей его ширине, в остальных точках ландшафт остается неизменным (см. рисунок).

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

Задание

Напишите программу ROCKS, которая поможет рабочим в их расчётах.

Входные данные

В первой строке входного файла ROCKS.DAT содержатся два целых числа: N - количество операций, которые будут выполнять рабочие (1≤N?100000), и L - длина прямоугольника (1≤L?100000).

В следующих N строках содержатся описания операций: первое число строки - номер операции, где "1" означает, что рабочие собираются поставить магический импульсатор, "2" - рабочие хотят узнать некоторый объём. Если операция имеет код "1", то далее идут два целых числа p и H (0≤p?L; 1≤H?L), то есть импульсатор силой H ставят в позицию p (на оси X). Если операция имеет код "2", то далее идут два целых числа A и B (0≤A<B?L); это означает, что рабочие хотят узнать объём части дамбы, которая находится над прямоугольником от A до B по оси X, и от 0 до 1 по оси Z.

Выходные данные

Создайте выходной файл ROCKS.SOL, в котором для каждой операции, указанной во входном файле, выведите строку со следующей информацией.

Если операция есть "1", то выведите число "-1" без кавычек. Если операция есть "2", то выведите число, равное объёму части дамбы, которая находится над прямоугольником от A до B по оси X, и от 0 до 1 по оси Z, как показано на рисунке.

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

ROCKS.DAT	ROCKS.SOL
2 13 1 7 5 2 5 9	-1 16

Прислать комментарий

Решение

Задача 98676

[Менеджер памяти]

Тема:

[

Куча

]

Сложность: 5
Классы: 8,9,10,11

Имя входного файла:

memory.in

Имя выходного файла:

memory.out

Максимальное время работы на одном тесте:

2 секунды

Максимальный объем используемой памяти:

64 мегабайта

Максимальная оценка за задачу:

100 баллов

Пете поручили написать менеджер памяти для новой стандартной библиотеки языка H++. В распоряжении у менеджера находится массив из N последовательных ячеек памяти, пронумерованных от 1 до N. Задача менеджера - обрабатывать запросы приложений на выделение и освобождение памяти.

Запрос на выделение памяти имеет один параметр K. Такой запрос означает, что приложение просит выделить ему K последовательных ячеек памяти. Если в распоряжении менеджера есть хотя бы один свободный блок из K последовательных ячеек, то он обязан в ответ на запрос выделить такой блок. При этом непосредственно перед самой первой ячейкой памяти выделяемого блока не должно располагаться свободной ячейки памяти. После этого выделенные ячейки становятся занятыми и не могут быть использованы для выделения памяти, пока не будут освобождены. Если блока из K последовательных свободных ячеек нет, то запрос отклоняется.

Запрос на освобождение памяти имеет один параметр T. Такой запрос означает, что менеджер должен освободить память, выделенную ранее при обработке запроса с порядковым номером T. Запросы нумеруются, начиная с единицы. Гарантируется, что запрос с номером T - запрос на выделение, причем к нему еще не применялось освобождение памяти. Освобожденные ячейки могут снова быть использованы для выделения памяти. Если запрос с номером T был отклонен, то текущий запрос на освобождение памяти игнорируется.

Требуется написать менеджер памяти, удовлетворяющий приведенным критериям.

Формат входных данных

Первая строка входного файла содержит числа N и M - количество ячеек памяти и количество запросов соответственно (1 ≤ N ≤ 2³¹ - 1; 1 ≤ M ≤ 10⁵). Каждая из следующих M строк содержит по одному числу: (i+1)-я строка входного файла (1 ≤ i ≤ M) содержит либо положительное число K, если i-й запрос - запрос на выделение с параметром K (1 ≤ K ≤ N), либо отрицательное число -T, если i-й запрос - запрос на освобождение с параметром T (1 ≤ T < i).

Формат выходных данных

Для каждого запроса на выделение памяти выведите в выходной файл результат обработки этого запроса: для успешных запросов выведите номер первой ячейки памяти в выделенном блоке, для отклоненных запросов выведите число -1. Результаты нужно выводить в порядке следования запросов во входном файле.

Пример

memory.in	memory.out
6 8 2 3 -1 3 3 -5 2 2	1 3 -1 -1 1 -1

Прислать комментарий

Решение

Задача 102933

[Прямоугольники ]

Темы:	[	Вычислительная геометрия (прочее)	]
Темы:	[	Очередь с приоритетами	]

Сложность: 3

На ось Ox плоскости Oxy положили N прямоугольников. Требуется найти координаты вершин ломаной, огибающей это множество прямоугольников сверху (см. рис.).

Входные данные
Первая строка входного файла содержит целое число N (1 ≤ N ≤ 100). Далее следуют N строк, в каждой из которых записана тройка вещественных чисел, описывающих очередной из прямоугольников. Первое из них задает абсциссу левого нижнего угла прямоугольника, а остальные два – его длину и высоту.

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

Пример входного файла
2
0 4 2
2 4 5

Пример выходного файла
6
0 0
0 2
2 2
2 5
6 5
6 0

Прислать комментарий Решение

Страница: 1 [Всего задач: 3]