Темы --> Информатика --> Структуры данных --> Деревья --> Дерево отрезков, RSQ, RMQ
---> 24 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: 1 2 3 4 5 >> Отображать по:
#554
Пирамида
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
32 megabytes

После победы в великой битве Король Ягуар хочет построить пирамиду, которая будет одновременно монументом в честь победы и гробницей для погибших солдат. Пирамида будет построена на поле боя. Она должна иметь прямоугольное основание, состоящее из \(a\) столбцов и \(b\) строк. Для сохранения останков и оружия павших солдат внутри основания пирамиды будет располагаться небольшая прямоугольная комната, состоящая из \(c\) столбцов и \(d\) строк.

Архитекторы Короля представили поле боя в виде прямоугольной сетки. Эта сетка состоит из квадратных клеток единичной площади и имеет \(m\) столбцов и \(n\) строк. Для каждой клетки они измерили ее высоту и получили некоторое целое число.

Основание пирамиды и комната должны покрывать включаемые ими клетки полностью, а их стороны должны быть параллельны сторонам поля боя. Высоты клеток, составляющих комнату, должны остаться неизменными, а высоты всех клеток основания пирамиды будут выровнены с помощью перемещения песка с более высоких клеток на более низкие. В результате этого высота основания пирамиды будет равна среднему арифметическому высот всех его клеток (за исключением клеток комнаты). Архитекторы могут выбрать любое местоположение для комнаты внутри пирамиды, но обязательно оставлять вокруг комнаты стену основания пирамиды толщиной хотя бы в одну клетку.

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

Задание

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

Ограничения

3 ≤ \(m\) ≤ 1000
3 ≤ \(n\) ≤ 1000
3 ≤ \(a\) ≤ \(m\)
3 ≤ \(b\) ≤ \(n\)
1 ≤ \(c\) ≤ \(a\) – 2
1 ≤ \(d\) ≤ \(b\) – 2
Все высоты – целые числа от 1 до 100.

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

Ваша программа получает входные данные в следующем формате:
СТРОКА 1: Содержит шесть целых чисел, разделенных пробелами, в следующем порядке: \(m\), \(n\), \(a\), \(b\), \(c\) и \(d\).
СЛЕДУЮЩИЕ \(n\) СТРОК: Каждая из этих строк содержит m целых чисел, разделенных пробелами. Эти числа соответствуют высотам клеток в одной строке сетки. Первая из этих строк соответствует верхней строке (строке 1) сетки, а последняя – нижней строке (строке \(n\)). При этом \(m\) чисел в каждой строке соответствуют высотам клеток этой строки, начиная со столбца 1.

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

Ваша программа должна вывести следующие данные:
СТРОКА 1: Должна содержать два целых числа, разделенные пробелом, – координаты левой верхней клетки основания пирамиды, при этом первое число соответствует столбцу, а второе – строке.
СТРОКА 2: Должна содержать два целых числа, разделенные пробелом, – координаты левой верхней клетки комнаты, при этом первое число соответствует столбцу, а второе – строке.

Замечание

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

Оценивание

Ряд тестов с общей суммой 30 баллов будет удовлетворять следующим ограничениям:
3 ≤ \(m\) ≤ 10
3 ≤ \(n\) ≤ 10

Примеры
Входные данные
8 5 5 3 2 1
1 5 10 3 7 1 2 5
6 12 4 4 3 3 1 5
2 4 3 1 6 6 19 8
1 1 1 3 4 2 4 5
6 6 3 3 3 2 2 2
Выходные данные
1
4 1
6 2
#1049
Горнолыжные соревнования
  
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes

Горнолыжник, готовясь к соревнованиям, нарисовал на бумаге схему горнолыжной трассы для выбора оптимального маршрута спуска. На схеме расположенные на трассе ворота представлены горизонтальными отрезками. Никакая пара ворот не имеет общих точек.

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

За каждые ворота, через которые не проходит маршрут, лыжнику начисляются штрафные очки. Общий штраф за спуск по маршруту вычисляется как сумма длины маршрута и штрафных очков за непройденные ворота.

Требуется написать программу, которая определяет, какой минимальный общий штраф горнолыжник может получить при прохождении трассы.

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

В первой строке входного файла задано число N - количество ворот на трассе (0 ≤ N ≤ 500), в следующих двух строках заданы Sx, Sy, Fx, Fy - координаты точек старта и финиша соответственно. В каждой из следующих N строк записаны четыре числа ai, bi, yi, ci - x-координаты левого и правого концов ворот, y-координата ворот и штраф за непрохождение данных ворот (ai < bi, Fy < yi < Sy, ci - целое число, 0 ≤ ci ≤ 10000). Все координаты - целые числа, не превосходящие по модулю 10000.

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

В выходной файл выведите наименьший возможный общий штраф за прохождение трассы с точностью не менее 4 знаков после десятичной точки.

Система оценки

Потестовая.

Примеры
Входные данные
4
3 6
3 1
5 7 4 1
4 5 5 10
1 2 4 5
2 5 2 0
Выходные данные
7.8126
#1638
Скалы
  

Ограничение по времени: 0.2 секунды

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

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

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

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

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

В первой строке входного файла содержатся два целых числа: 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\).

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

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

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

Примеры
Входные данные
2 13
1 7 5
2 5 9
Выходные данные
-1
16
#1656
Прямоугольники
  
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
64 megabytes

Дана последовательность N прямоугольников различной ширины и высоты (wi,hi). Прямоугольники расположены, начиная с точки (0, 0), на оси ОХ вплотную друг за другом (вправо). Требуется найти M - площадь максимального прямоугольника (параллельного осям координат), который можно вырезать из этой фигуры.

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

В первой строке задано число N (1 ≤ N ≤ 8000). Далее идет N строк. В каждой строке содержится два числа: ширина и высота i-го прямоугольника. Значение , 0 < hi ≤ 3*104.

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

Вывести одно число М. Значение M не превосходит 2*109.

Примеры
Входные данные
3
4 3
2 1
2 5
Выходные данные
12
Входные данные
3
4 3
2 1
3 5
Выходные данные
15
#1663
Суперминимум
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дано N чисел. Для каждых K подряд идущих чисел найти минимальное среди них.

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

В первой строке даны числа N и K (1 ≤ N ≤ 150000, 1 ≤ K ≤ 10000, K ≤ N), разделенные пробелом. Во второй строке записано N целых чисел через пробел. Числа находятся в диапазоне от -32768 до 32767.

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

Для каждых К подряд идущих чисел вывести минимальное из них.

Пример

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

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

11 3

8 764 1 3 85 2 4 5 77 1 5

1 1 1 2 2 2 4 1 1

     

Страница: 1 2 3 4 5 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест