--->
90 задач
<---
Источники
Петя пишет программы для бирж. Он занимается разработкой различных финансовых инструментов, его последний проект связан с анализом возможности арбитража с использованием исторических данных о котировках существенно волатильной акции.
Идея анализа состоит в следующем: по заданным котировкам акции в течение n последовательных дней, требуется выбрать подпоследовательность котировок, которая удовлетворяет следующему свойству: любые две соседние котировки в выбранной подпоследовательности должны отличаться не менее чем на k . Например, если котировки равны, соответственно, 1014, 1024, 1034, 1045, 1030, 998 и k = 15 , то подпоследовательность котировок 1014, 1034, 998 является допустимой. Выбранная подпоследовательность должны быть как можно длиннее. Так, в приведенном примере выбранная последовательность не является оптимальной, подпоследовательность 1014, 1045, 1030, 998 лучше.
По заданной последовательности котировок, найдите ее длиннейшую допустимую подпоследовательность.
Первая строка входного файла содержит число n ( 1 ≤ n ≤ 100000 ) количество котировок и k ( 1 ≤ k ≤ 10 9 ). Вторая строка содержит n целых чисел последовательность котировок (все котировки находятся в интервале от 1 до 10 9 включительно).
Первая строка выходного файла должна содержать l — длину оптимальной подпоследовательности. Вторая строка должна содержать l целых чисел элементы любой такой подпоследовательности.
6 15 1014 1024 1034 1045 1030 998
4 1014 1045 1030 998
Дано клетчатое поле N x M, все клетки поля изначально белые. Автомат умеет:
Дана последовательность команд для автомата. Требуется выполнить эти команды в указанной последовательности, и для каждой команды запроса ближайших белых соседей указать результат ее выполнения.
начала вводятся размеры поля N и M ( 1 ≤ N ≤ 20 , 1 ≤ M ≤ 50000 ), затем количество команд K ( 1 ≤ K ≤ 10 5 ), а затем сами команды. Команды записаны по одной в строке в следующем формате:
На каждый запрос Neighbors требуется вывести сначала количество ближайших белых соседей (или 0 , если ни с одной из сторон белых клеток не осталось), а затем их координаты (соседей можно перечислять в произвольном порядке). Если запросов Neighbors нет, ничего выводить не надо.
5 5 10 Neighbors 3 1 Color 4 1 Color 2 4 Color 4 5 Color 2 2 Neighbors 5 4 Neighbors 5 5 Neighbors 2 4 Color 3 5 Neighbors 3 5
3 2 1 4 1 3 2 3 4 4 5 3 5 5 2 3 5 5 4 4 1 4 3 4 2 3 2 5 3 2 5 5 5 3 4
Дан трёхмерный массив. Найдите сумму на параллелепипеде со сторонами, паралельными осям координат.
В первой строке даны три числа: 1 ≤ N , M , K ≤ 100 . В следующих N × M строках даны по K чисел - | a ijk | < 10 9 . Далее в отдельной строке даётся одно число Q ≤ 10 9 - количество запросов. В следующих Q строках даются запросы: каждый запрос имеет вид x 1 y 1 z 1 x 2 y 2 z 2 - две противоположные границы параллелепипеда, сумму которого необходимо подсчитать. 1 ≤ x 1 ≤ x 2 ≤ N 1 ≤ y 1 ≤ y 2 ≤ M 1 ≤ z 1 ≤ z 2 ≤ K
Для каждого запроса выведите одно число в отдельной строке - ответ на этот самый запрос
3 3 3 2 3 5 1 2 3 4 5 7 1 6 6 9 6 6 8 6 6 4 3 3 2 3 3 5 3 3 1 2 1 2 3 3 3
54
В супермаркете «На троечку» часто происходят распродажи товаров, срок годности которых подходит к концу. Каждый товар привозят в магазин в определенное время, а через некоторое его вывозят из магазина, в связи с окончанием срока годности. Более формально, каждый товар имеет стоимость c i , время его завоза в магазин a i и время его вывоза из магазина b i .
У Иннокентия есть хитрый план похода в магазин. Даже несколько. Каждый план похода в магазин выглядит так: Иннокентий выбирает какое-то время, когда он появится в магазине m j , время s j , которое он проведет в магазине среди огромных стеллажей товаров, и сумму денег k j , которую он рассчитывает потратить. Для каждого плана он хочет узнать, сможет ли он осуществить его, т. е. верно ли, что он сможет во время своего пребывания в магазине купить несколько товаров суммарной стоимостью ровно k j , при этом все выбранные товары должны быть в магазине на протяжении всего пребывания Иннокентия в магазине.
Помогите Иннокентию определить, какие из его планов можно выполнить.
В первой строке входных данных содержится число N — общее количество товаров в магазине ( 1 ≤ N ≤ 500 ). Далее содержатся описания товаров, каждый товар описывается тремя целыми числами c i , a i , b i , обозначающими стоимость товара, время его завоза и время его вывоза из магазина ( 1 ≤ c i ≤ 1 000 , 1 ≤ a i < b i ≤ 10 9 ).
Далее содержится число M — количество планов Иннокентия ( 1 ≤ M ≤ 500 000 ). Каждый план описывается тремя целыми числами m j , k j , s j , обозначающими время прихода Иннокентия в магазин, сумму денег, которую он готов потратить в этом плане и длительность его пребывания в магазине ( 1 ≤ m j ≤ 10 9 , 1 ≤ k j ≤ 100 000 , 0 ≤ s j ≤ 10 9 ).
Помните, что это только планы, т. е. ситуация в магазине не меняется вне зависимости от того, может ли Иннокентий осуществить план или нет.
Для каждого плана в отдельной строке выведите « YES », если Иннокентий может его осуществить, и « NO » в противном случае.
Тесты к этой задаче состоят из четырех групп.
Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы.
5 6 2 7 5 4 9 1 2 4 2 5 8 1 3 9 5 2 7 1 2 7 2 3 2 0 5 7 2 4 1 5
YES NO YES YES NO
Лука - торговец картинами. У него есть N клиентов, каждому из которых он продает произведения искусства. Каждый клиент может купить либо цветные картины, либо черно-белые, но не те и другие вместе. При этом клиент под номером i готов купить не более a i цветных картин и не более b i черно-белых картин. При этом каждый клиент хочет купить хотя бы одну картину.
У Луки практически неограниченный запас картин, поэтому запросы клиентов не являются для него проблемой. Однако, Лука не любит продавать черно-белые картины, и если окажется, что меньше, чем C людей купили цветные картины, он очень огорчится.
В силу нестабильной экономической ситуации в стране клиенты постоянно изменяют свои запросы, иными словами количество цветных и черно-белых картин, которые они готовы купить. Из-за этого Лука постоянно задается вопросом: "Сколько у меня есть вариантов, как продать клиентам картины, чтобы хотя бы C человек купили цветные картины?". Помогите Луке и защитите его от излишнего беспокойства.
Первая строка содержит два целых числа N и C ( 1 ≤ N ≤ 105, 1 ≤ C ≤ 20 ). Вторая строка содержит N целых чисел a i ( 1 ≤ a i ≤ 109 ). Третья строка содержит N целых чисел b i ( 1 ≤ b i ≤ 109 ). Четвертая строка содержит одно целое число Q ( 1 ≤ Q ≤ 105 ) - количество изменений требований клиентов. Каждая из следующих Q строк содержит три числа: номер клиента, меняющего требования P ( 1 ≤ P ≤ N ), новое максимальное количество цветных картин, которое он готов купить A p ( 1 ≤ A p ≤ 109 ) и новое максимальное количество черно-белых картин, которое он готов купить B p ( 1 ≤ B p ≤ 109 ).
Выведите Q строк, где в q -й строке записано единственное число - количество вариантов продать картины клиентам, чтобы хотя бы C человек купили цветные картины, по модулю 10007 после первых q изменений требований.
Разбалловка для личной олимпиады
Тесты 4-6 — числа n, q не превосходят 1000. Группа тестов оценивается в 30 баллов.
Тесты 7-13 — Полные ограничения. Группа тестов оценивается в 70 баллов.
2 2 1 1 1 1 1 1 1 1
1
2 2 1 2 2 3 2 1 2 2 2 2 2
4 4
4 2 1 2 3 4 1 2 3 4 1 4 1 1
66