---> 80 задач <---
Источники
    Личные олимпиады(925 задач)
    Командные олимпиады(684 задач)
Страница: 1 2 3 4 5 6 7 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Над двумерной таблицей введена операция A, которая по координатам клетки, направлению и числу, прибавляет это число ко всем ячейкам от начальной в заданном направлении. Также определена операция B, которая вызывает операцию A для всех ячеек заданного прямоугольника.

Специальный терминал, разработанный в лаборатории, где работает Дима, представляет собой горизонтальный прямоугольник, состоящий из m×n ячеек, каждая из которых может содержать произвольное целое число. Ячейки занумерованы парами чисел, левая верхняя ячейка имеет номер (1, 1), правая нижняя – ($m$, $n$).

Специальное устройство ввода, сконструированное специально для этого терминала, позволяет отправлять терминалу две команды: $A$($r$, $c$, $d$, $v$) и $B$($r_1$, $c_1$, $r_2$, $c_2$, $d$, $v$).

Рассмотрим сначала команду $A$. Параметры $r$ и $c$ изменяются в пределах от 1 до $m$ и от 1 до $n$ соответственно и указывают, к какой ячейке применяется команда. Параметр $d$ может принимать значение из множества {$L$, $R$, $U$, $D$} и задает направление, в котором применяется команда: влево, вправо, вверх или вниз соответственно. Параметр $v$ представляет собой целое неотрицательное число. В результате выполнения команды значения во всех ячейках, находящихся в направлении $d$ от ячейки ($r$, $c$), включая эту ячейку, увеличиваются на $v$.

Например, если терминал имеет размер 5×4, то после выполнения команды $A$(3, 2, $R$, 3) значения в ячейках (3, 2), (3, 3) и (3, 4) увеличатся на 3, а после команды $A$(2, 1, $U$, 2) значения в ячейках (2, 1) и (1, 1) увеличатся на 2.

Рассмотрим теперь команду $B$. Первые четыре ее параметра являются целыми числами и удовлетворяют условиям 1$ \le$ $r_1$ $\le$ $r_2$ $\le$ $m$ и 1$ \le$ $c_1$ $\le$ $c_2$ $\le$ $n$. Параметры $d$ и $v$ могут принимать те же значения, что и соответствующие параметры команды $A$. Команда $B$ выполняется следующим образом: для всех пар ($r$, $c$), таких, что $r_1$ $\le$ $r$ $\le$ $r_2$ и $c_1$ $\le$ $c$ $\le$ $c_2$ выполняется команда $A$($r$, $c$, $d$, $v$).

Исходно все ячейки терминала содержат нули. Выведите содержимое терминала после выполнения заданной последовательности команд.

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

В первой строке вводятся числа $m$ и $n$, ( 1$ \le$m, n$ \le$200). В следующей строке задается число $k$ – количество команд, которые следует обработать ( 0$ \le$k$ \le$40 000). Далее идут $k$ строк, содержащих описания команд. Первый символ каждой строки задает тип команды, затем следует пробел и параметры команды, каждые два последовательных параметра разделены ровно одним пробелом. Параметр $v$ каждой команды неотрицателен и не превышает 100.

Общее число команд $A$, которое потребуется выполнить на терминале, включая команды, которые придется выполнить при выполнении команд $B$, не превышает 5 * $10^6$.

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

Выведите $m$ строк по $n$ чисел в каждой – содержимое терминала после выполнения указанной последовательности команд.

Примеры
Входные данные
5 4
4
A 2 2 D 1
A 3 4 L 2
B 2 3 3 4 U 13
B 1 1 2 1 R 5
Выходные данные
5 5 31 31 
5 6 31 31 
2 3 15 15 
0 1 0 0 
0 1 0 0 
ограничение по времени на тест
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
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

В этой задаче Вам вновь придется помочь Берляндии. Эта страна состоит из $n$ городов, некоторые пары из которых соединены двусторонними дорогами, каждая дорога характеризуется своей длиной. Все города пронумерованы числами от 1 до $n$, столица имеет номер 1. Время от време ни Президент объезжает страну, посещая города страны. Целью каждой поездки является один из городов, к которому он едет из столицы вдоль дорог одним из кратчайших путей.

В далекие времена (когда задачи на алгоритм Дейкстры вызывали сложность) специальное ведомство составила такой набор дорог $T$, вдоль которого можно было проехать из столицы в любой город, причем единственным образом. Разумеется, путь по дорогам из набора $T$ из столицы в каждый город являлся кратчайшим. Особо умные жители страны попросту называли этот набор дорог "деревом кратчайших путей". Известно, что Президент пользовался дорогами из $T$ во время своих поездок. За прошедшие годы этот набор перестал быть секретным, и, поэтому, стал объектом повышенного внимания берляндских экстремистов. У специального ведомства новое задание. Для каждого города кроме столицы необходимо вычислить кратчайшее расстояние до него, при условии, что та дорога по которой Президент должен был закончить свой путь в этот город является атакованной и проезжать по ней нельзя.

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

В первой строке входного файла записана пара целых чисел $n$ и $m$ ($2 \leq n \leq 4\,000$; $ n - 1 \leq m \leq 100\,000$), где $n$ — количество городов в стране, а $m$— количество дорог в этой стране. Далее в $m$ строках содержатся описания дорог, по одной дороге в строке. Каждая дорога задается четверкой целых чисел $a_j$, $b_j$, $l_j$, $t_j$ , где $a_j$, $b_j$ это номера городов, соединяемых дорогой ($1 \leq a_j, b_j \leq n$; $a_j \neq b_j$), $l_j$ — ее длина ($1 \leq l_j \leq 10^5$), а $t_j$ равно 1 если дорога принадлежит дереву кратчайших путей и 0 в противном случае.

Гарантируется, что набор $T$ удовлетворяет описанным выше свойствам. Между парой городов может быть более одной дороги. Все дороги двусторонние.

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

Выведите $n - 1$ число в строку через пробелы. $i$-ое число должно быть равно либо длине кратчайшго пути из столицы в город $i + 1$, при условии, что по той дороге из $T$, которой Президент заканчивал свой путь в этот город, передвигаться нельзя, либо -1, если добраться до города $i + 1$ вообще невозможно.

Примеры
Входные данные
5 9
3 1 3 1
1 4 2 1
2 1 6 0
2 3 4 0
5 2 3 0
3 2 2 1
5 3 1 1
3 5 2 0
4 5 4 0
Выходные данные
6 7 8 5
ограничение по времени на тест
1.5 second;
ограничение по памяти на тест
64 megabytes

Реализуйте структуру данных, которая на данном массиве из N целых чисел позволяет узнать максимальное значение на этом массиве и индекс элемента, на котором достигается это максимальное значение.

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

В первой строке вводится натуральное число N (1 ≤  N ≤ 105) – количество элементов в массиве. В следующей строке содержатся N целых чисел, не превосходящих по модулю 109 – элементы массива. Далее идет число K  (0 ≤ K ≤ 105) – количество запросов к структуре данных. Каждая из следующих K строк содержит два целых числа l и r (1 ≤ l ≤ r ≤ N) – левую и правую границы отрезка в массиве для данного запроса.

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

Для каждого из запросов выведите два числа: наибольшее значение среди элементов массива на отрезке от l до r и индекс одного из элементов массива, принадлежащий отрезку от l до r, на котором достигается этот максимум.

Примеры
Входные данные
5
7 3 1 6 4
3
1 5
2 4
3 3

Выходные данные
7 1
6 4
1 3
Входные данные
1
0
1
1 1
Выходные данные
0 1
Входные данные
2
0 1
3
1 1
1 2
2 2
Выходные данные
0 1
1 2
1 2
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Отрезок целочисленной прямой длины N разбит на единичные отрезки, которые пронумерованы от 1 до N.

Их объединяют в группы по следующим правилам:
1. Несколько подряд идущих отрезков, ни один из которых не принадлежит ни одной из групп, могут быть объединены в группу.
2. Любая ранее созданная группа может быть уничтожена, при этом входившие в нее отрезки больше не относятся ни к какой группе и могут впоследствии быть отнесены к другим группам.

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

Каждую группу можно идентифицировать парой чисел: номером первого и номером последнего отрезка, входящего в группу.

Первоначально нет ни одной группы.

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

Первая строка входных данных содержит число N – количество отрезков и число K – количество запросов (1 ≤ NK ≤105). Далее идет K строчек, содержащих запросы к структуре данных. Каждый запрос начинается с числа 1 (запрос на создание группы) или 2 (запрос на удаление группы). После числа 1 указывается два других числа l и r (1 ≤ l ≤ r ≤ N), после числа 2 указывается одно число i (1 ≤ i ≤ N).

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

Для каждого запроса типа 1 необходимо отрезки с номерами от l до r объединить в группу. Если все эти отрезки не входят ни в одну группу, запрос считается удачным и программа должна вывести 1. Если хотя бы один из этих отрезков уже относится к какой-то группе, запрос считается неудачным, объединение не производится и программа выводит 0.

Для каждого запроса типа 2 необходимо удалить группу, в которую входит отрезок с номером i, при этом программа должна вывести два числа: номер первого и последнего отрезка, входящих в удаляемую группу. Если отрезок с номером i не относится ни к одной группе, программа должна вывести два нуля.

Примеры
Входные данные
5 6
1 1 2
1 4 5
1 2 4
2 5
2 1
2 4

Выходные данные
1
1
0
4 5
1 2
0 0

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