Префиксные суммы(минимумы, ...)

107 задач
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Выбросы#93430

Дана последовательность вещественных чисел \(a_1, a_2, \dots, a_N\) и целое число \(K\). Для каждого индекса \(i\), удовлетворяющего условию \(K+1 \le i \le N-K\), рассмотрим множество его \(2K\) соседей: \[S_i = \{ a_{i-K}, \dots, a_{i-1}, a_{i+1}, \dots, a_{i+K} \}.\] Вычислим среднее арифметическое элементов этого множества: \[\mu_i = \frac{1}{2K} \sum_{x \in S_i} x\] и их стандартное отклонение: \[\sigma_i = \sqrt{ \frac{1}{2K} \sum_{x \in S_i} (x - \mu_i)^2 }.\] Элемент \(a_i\) называется выбросом, если выполняется неравенство \[|a_i - \mu_i| > 2\sigma_i.\] Если \(\sigma_i = 0\) (все числа в \(S_i\) равны), то условие превращается в \(|a_i - \mu_i| > 0\), то есть \(a_i\) считается выбросом, когда он отличается от этого общего значения.

Требуется определить количество выбросов среди всех элементов, для которых определена окрестность (т. е. для \(i = K+1, K+2, \dots, N-K\)).

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

Входные данные
Первая строка содержит два целых числа \(N\) и \(K\) (\(1 \le K \le \lfloor N/2 \rfloor\), \(N \le 200\,000\)). Вторая строка содержит \(N\) вещественных чисел \(a_1, a_2, \dots, a_N\), разделенных пробелами

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

Выведите одно целое число — количество выбросов.
 

Примеры
№ Входные данные Выходные данные
1 8 2
-0.87270147 -0.34887844 0.95993054 -0.51785580 -0.44876428 0.94608416 -0.30955386 2.16387322		 1

Примечание
Ваш балл за задачу — это доля пройденных верно тестов. Пример из условия не входит в число оцениваемых тестов.

 

Префиксные суммы(минимумы, ...)
✓ 7✗ 170900средняяВойти и решать
Why Did the Cow Cross the Road II#90433
Длинная дорога через ферму Джона имеет \(N\) перекрёстков, последовательно пронумерованных \(1 \ldots N\) (\(1 \leq N \leq 100,000\)). Чтобы помочь коровам переходить дорогу на этих перекрёстках, ФД установил светофоры, на которых загорается зелёная корова, когда коровам можно идти, и красная - в противном случае. К несчастью, большой электрический шторм повредил некоторые из этих светофоров. По списку повреждённых светофоров, вычислите минимальное количество светофоров, которое ФД должен восстановить, чтобы существовал непрерывный блок из не менее \(K\) работающих светофоров.

ФОРМАТ ВВОДА (файл maxcross.in):

Первая строка ввода содержит \(N\), \(K\) и \(B\) (\(1 \leq B, K \leq N\)). Следующие \(B\) строк описывают номер сломанного светофора.

ФОРМАТ ВЫВОДА (файл maxcross.out):

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

Префиксные суммы(минимумы, ...)
—Войти и решать
Why Did the Cow Cross the Road#90429

Фермер Джон растит \(N\) пород коров (\(1 \leq N \leq 100,000\)), каждое из его полей предназначено для пастбища одной специфической породы коров, например, поле предназначенное для коров породы 12 может быть использовано только для коров породы 12 и не может быть использовано для коров других пород. Длинная дорога идёт вдоль фермы. Имеется последовательность из \(N\) полей вдоль одной стороны дороги (по одному для каждого типа коров) и \(N\) полей вдоль другой стороны дороги (тоже по одному для каждого типа коров). Когда корова пересекает дорогу, она переходит из одного поля, предназначенного для этой породы коров в другое поле, предназначенное для этой породы коров.

Если бы ФД "подумал вперёд" он мог бы упорядочить поля под породы таким образом, чтобы поля для одной и той же породы по разные стороны дороги находились друг напротив друга, и никакие коровы не могли бы столкнуться при переходе дороги. Однако упорядочивание полей по породам с разных сторон дороги может быть и различным, и тогда могут быть пары пород, для которых их пути пересекаются при переходе дороги. Пара различных пород \((a,b)\) называется "пересекающейся", если любой путь через дорогу для коровы породы \(a\) должен пересекаться с любым путём через дорогу для коровы породы \(b\).

ФД хочет минимизировать количетво пересекающихся пар пород. По логистическим причинам ФД может перемещать коров "по кругу" на одной стороне дороги, так что поля осуществляют "циклический сдвиг". То есть для некоторого \(0 \leq k < N\), каждая корова перемещается на \(k\) полей вперёд, а коровы из последних \(k\) полей пермещаются в первые \(k\) полей. Например, если поля на одной стороне дороги упорядочены так: 3, 7, 1, 2, 5, 4, 6 и выполняется сдвиг на \(k=2\), то новый порядок будет такой: 4, 6, 3, 7, 1, 2, 5. Определите минимальное возможное количество пересекающихся пар пород, которые могут существовать после соответствующего циклического сдвига полей на одной стороне дороги.

ФОРМАТ ВВОДА (файл mincross.in):

Первая строка содержит число \(N\). Следующие \(N\) строк описывают порядок, по номерам пород на полях вдоль первой стороны дороги. Каждый номер породы - целое число в интервале \(1 \ldots N\). Последние \(N\) строк описывают порядок, по номерам пород коров, полей на другой стороне дороги.

ФОРМАТ ВЫВОДА (фвйл mincross.out):

Выведите минимальное количество пересекающихся пар пород коров после циклического сдвига полей на одной стороне дороги (любая сторона может сдвигаться).

Префиксные суммы(минимумы, ...)
—Войти и решать
Why Did the Cow Cross the Road III#90428
Ферма Джона имеет большую круглую дорогу по периметру главного поля, на котором его коровы пасутся каждый день. Каждое утро коровы переходят через эту дорогу, идя в поле, а каждый вечер переходят дорогу ещё раз, возвращаясь в амбар.

Как известно, коровы - существа привычки, поэтому они переходят дорогу одним и тем же способом каждый день. Каждая корова приходит в поле в точке, отличающейся от той, в которой она с него уходит, и все эти точки для разных коров также отличаются друг от друга. У ФД есть \(N\) коров, последовательно пронумерованных \(1 \ldots N\), Поэтому имеется ровно \(2N\) точек у дороги. ФД выписал все эти точки по номерам коров, по часовой стрелке, сформировав последовательность из \(2N\) чисел, каждое из которых встречается в этой последовательности ровно дважды. Он не записывал, является ли эта точка точкой входа или точкой выхода.

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

ФОРМАТ ВВОДА (файл circlecross.in):

Первая строка ввода содержит \(N\) (\(1 \leq N \leq 50,000\)), а последующие \(2N\) строк описывают номера коров в последовательности входов и выходов вокруг поля.

ФОРМАТ ВЫВОДА (файл circlecross.out):

Выведите количество пересекающихся пар.

Префиксные суммы(минимумы, ...)
—Войти и решать
Circular Barn#90414
Будучи фанатом современной архитектуры, Фермер Джон построил новый амбар в форме круга. Внутри амбар составляет кольцо из \(n\) комнат, пронумерованных по часовой стрелке \(1 \ldots n\) по периметру (\(3 \leq n \leq 100,000\)). Каждая комната имеет двери в две соседние комнаты, а также дверь из амбара во внешний мир.

У ФД есть ровно \(n\) коров, и он хочет поместить по одной корове в каждую комнату. Однако своенравные коровы выстроились не как нужно, и возможно несколько коров собрались у одной внешней двери. А именно, \(c_i\) коров стоит перед дверью с номером \(i\). Разумеется, \(\сумма c_i = n\).

Чтобы коровы добрались до своих мест ФД собирается применить следующий подход: каждая корова входит в дверь, перед которой она стоит и идёт по часовой стрелке в свою комнату. В предположении, что проход коровы через \(d\) дверей отнимает у неё \(d^2\) энергии, определите минимальное количество энергии, которое требуется, чтобы распределить коров по одной в комнату.

ФОРМАТ ВВОДА (файл cbarn.in):

Первая строка ввода содержит \(n\). Оставшиеся \(n\) строк содержат \(c_1 \ldots c_n\).

ФОРМАТ ВЫВОДА (файл cbarn.out):

Выведите минимальное количество энергии, потреблённое всеми коровами.

Жадный алгоритмПрефиксные суммы(минимумы, ...)
—Войти и решать
Hoof, Paper, Scissors#90400
Возможно Вы слышали об игре "Камень, Бумага, Ножницы". Коровы любят играть в похожую игру "Копыто, Бумага, Ножницы" Правила игры "Копыто, Бумага, Ножницы" просты. Две коровы играют друг против друга. Они обе считают до трёх, а затем одновременно делают жест, представляющий копыто, бумагу или ножницы. Копыто выигрывает у ножниц, ножницы выигрывают у бумаги, бумага выигрывает у копыта. Конечно может быть и ничья, если обе коровы сделали один и тот же жест.

Фермер Джон хочет сыграть с Бесси \(N\) раз (\(1 \leq N \leq 100,000\)). Бесси будучи экспертом в этой игре может предсказать каждый из жестов ФД. Но как корова, она очень ленива. Поэтому она хочет играть одним и тем же жестом переключившись на другой не более одного раза за все игры. Например, она может играть "Копыто" первые \(x\) игр, и затем переключится на "бумагу" на оставшиеся \(N-x\) игр.

По заданной последовательности жестов ФД, определите максимальное количество игр, которое выиграет Бесси.

ФОРМАТ ВВОДА (файл hps.in):

Первая строка ввода содержит число \(N\).

Оставшиеся \(N\) строк содержат жесты ФД, представленные символами H, P, S.

ФОРМАТ ВЫВОДА (файл hps.out):

Выведите максимальное количество игр, которое может выиграть Бесси, если она может переключать жест не более одного раза.

Задачи на моделированиеПрефиксные суммы(минимумы, ...)
—Войти и решать
Subsequences Summing to Sevens#90389
\(N\) коров Фермера Джона выстроены в ряд. Каждая корова помечена различным целым числом - идентификатором. ФД хочет сделать фото непрерывной группы коров, но он делает фотографию группы коров, только если сумма их идентификаторов делится на 7.

Помогите ФД определить размер наибольшей группы коров, которую он сможет сфотографировать.

ФОРМАТ ВВОДА (файл div7.in):

Первая строка ввода содержит \(N\) (\(1 \leq N \leq 50,000\)). Каждая из следующих \(N\) строк содержит идентификатор коровы (все в интервале \(0 \ldots 1,000,000\)).

ФОРМАТЫ ВЫВОДА (файл div7.out):

Выведите количество коров в наибольшей непрерывной группе коров, такой что сумма их идентификаторов делится на 7. Если такой группы нет, выведите 0.

Сумма может не поместится в 32-битное целое, Вы можете использовать 64-битное целое ("long long" в C/C++).

Префиксные суммы(минимумы, ...)
—Войти и решать
Fort Moo#90384
Беси строит форт прямоугольной формы.

Она уже выбрала место - кусок земли \(N\) метров по \(M\) метров (\(1 \leq N, M \leq 200\)). К несчастью, на этом месте есть болотистые участки, на которых строительство невозможно. Помогите Беси определить наибольшую (по площади) область, на которой можно построить форт, так , чтобы форт не проходил через болотистые участки.

ФОРМАТ ВВОДА (файл fortmoo.in):

Строка 1 содержит целые числа \(N\) и \(M\).

Следующие \(N\) строк содержат по \(M\) символов, формируя решётку, описывающую выбранное место. Символ '.' представляет траву, а символ 'X' представляет болотистую местность.

ФОРМАТ ВЫВОДА (файл fortmoo.out):

Единственное целое число, представляющее максимальную площадь, которую Беси может покрыть своим фортом.

Задачи на моделированиеПрефиксные суммы(минимумы, ...)
—Войти и решать
Breed Counting#90353
\(N\) коров Фермера Джона, последовательно пронумерованных от \(1 \ldots N\), выстроены в ряд. Каждая корова имеет ID породы: 1 - Holsteins, 2 - Guernseys, 3 - Jerseys. ФД просит Вас посчитать количество коров каждой породы, внутри некоторого интервала этого порядка.

ФОРМАТ ВВОДА (файл bcount.in):

Первая строка ввода содержит \(N\) и \(Q\) (\(1 \leq N \leq 100,000\), \(1 \leq Q \leq 100,000\)).

Следующие \(N\) строк содержат целое число 1,2, или 3 - ID породы соответствующей коровы.

Следующиеt \(Q\) строк описывают запрос в виде двух целых чисел \(a, b\) (\(a \leq b\)).

ФОРМАТ ВЫВОДА (файл bcount.out):

Для каждого из \(Q\) запросов \((a,b)\), выведите строку, содержащую три целых числа количество коров в интервале \(a \ldots b\), имеющих номера пород 1,2,3.

Префиксные суммы(минимумы, ...)
—Войти и решать
Breed Counting#90342
\(N\) коров Фермера Джона, последовательно пронумерованных от \(1 \ldots N\), выстроены в ряд. Каждая корова имеет ID породы: 1 - Holsteins, 2 - Guernseys, 3 - Jerseys. ФД просит Вас посчитать количество коров каждой породы, внутри некоторого интервала этого порядка.

ФОРМАТ ВВОДА (файл bcount.in):

Первая строка ввода содержит \(N\) и \(Q\) (\(1 \leq N \leq 100,000\), \(1 \leq Q \leq 100,000\)).

Следующие \(N\) строк содержат целое число 1,2, или 3 - ID породы соответствующей коровы.

Следующиеt \(Q\) строк описывают запрос в виде двух целых чисел \(a, b\) (\(a \leq b\)).

ФОРМАТ ВЫВОДА (файл bcount.out):

Для каждого из \(Q\) запросов \((a,b)\), выведите строку, содержащую три целых числа количество коров в интервале \(a \ldots b\), имеющих номера пород 1,2,3.

Префиксные суммы(минимумы, ...)
—Войти и решать
Marathon#90331

Беси спланировала марафон, специфицировав N контрольных точек
(1 <= N <= 100,000), которые нужно последовательно посетить.

Она поняла, что другие коровы могут не захотеть бежать весь маршрут.
Поэтому она хочет узнать, какую длину имеют определённые подмаршруты.
Подмаршрутом она называет непрерывную подпоследовательность
контрольных точек полного маршрута. Она знает также, что некоторые коровы
могут выбрать пропустить одну контрольную точку во время пробега по
подмаршруту (им не позволяется пропустить первую или последнюю контрольную
точку подмаршрута).

Для того чтобы построить наилучший маршрут Беси хочет исследовать
последствия выполнения изменений в месторасположения контрольных точек
её текущего маршрута. Помогите ей определить, как определённые изменения
расположения контрольных точек влияют на время, требуемое для прохождения
различных подмаршрутов (принимая во внимание, что коровы могут выбрать
пропуск одной контрольной точки во время пробега по подмаршруту).

Поскольку марафон проходит на улицах Манхэттена, расстояние между двумя
контрольными точками с координатами (x1, y1) и (x2, y2) надо вычислять
как манхэттенское: |x1-x2| + |y1-y2|.

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

В первой стоке хадаются N и Q (1 <= Q <= 100,000).
Последующие N строк содержат (x,y)- положение N контрольных точек в порядке
их посещения вдоль маршрута. Все координаты в интервале -1000 .. 1000.
Последующие Q строк состоят из изменений и запросов по одному в строке,
которые необходимо обрабатывать в том порядке, в котором они заданы.
Эти строки имеют вид "U I X Y" или "Q I J".

Строка в форме "U I X Y" указывает, что местоположение точки с номером
I (1 <= I <= N) должно быть изменено на (X Y).

Строка в форме "Q I J" спрашивает минимальное время прохождения подмаршрута
от контрольной точки I до контрольной точки J (I<=J), с учётом того, что
коровы могут выбрать пропустить одну контрольную точку вдоль этого подмаршрута
(кроме точек I и J).

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

Для каждого подмаршрута выведите требуемую длину на отдельной строке.

Префиксные суммы(минимумы, ...)
—Войти и решать
Marathon#90328

Фермер Джон отправил Беси на марафон.
Дистанция включает N (3 <= N <= 100,000) контрольных пунктов,
которые нужно посетить поочерёдно, от 1 до N.
Ленивая Беси решила пропустить один контрольный пункт
(не 1 и не N разумеется).

Помогите Беси найти минимальное расстояние, которое ей придётся
пробежать, если она пропустит один контрольный пункт.

Замечание: расстояние между двумя точками (x1,y1) и (x2,y2)
надо рассматривать и вычислять как манхэттенское
|x1-x2| + |y1-y2|,
поскольку во время этого марафона двигаться можно только
параллельно осям координат.

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

Первая строка даёт значение N.

Каждая из последующих N строк содержит два разделённых
пробелом целых числа X и Y (-1000 <= x <= 1000, -1000 <= y <= 1000),
представляющих контрольный пункт.

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

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

Когда Беси пропускает контрольную точку, она пропускает её,
а не все контрольные точки, расположенные в этой позиции.

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

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

В приведенном примере, пропустив точку(8,3) получим
минимальное расстояние 14.

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

14

Задача на реализациюПрефиксные суммы(минимумы, ...)
—Войти и решать
Farmer John's Favorite Operation#90311

У Фермера Джона есть массив \(a\) из \(N\) (\(1 \leq N \leq 2 \cdot 10^5\)) неотрицательных целых чисел и целое число \(M\) (\(1 \leq M \leq 10^9\)). Затем ФД спрашивает у Беси число \(x\). За одну операцию ФД может выбрать индекс \(i\) и вычесть или прибавить \(1\) к \(a_i\). ФД называет число скучным - если оно равно минимальному количеству операций, которые он должен выполнить, чтобы \(a_i-x\) стало делится на \(M\) для всех \(1 \leq i \leq N\).

Среди всех возможных \(x\) выберите минимально возможное скучное число.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит \(T\) (\(1 \leq T \leq 10\)), количество независимых подтестов.

Первая строка каждого подтеста содержит числа \(N\) и \(M\).

Вторая строка каждого подтеста содержит \(a_1, a_2, ..., a_N\) (\(0 \leq a_i \leq 10^9\)).

Гарантируется, что сумма \(N\) по всем подтестам не превысит \(5 \cdot 10^5\).

ФОРМАТ ВЫВОДА (на экран / stdout):

Для каждого подтеста выведите целое число - минимальное скучное число по всем возможным \(x\).

Префиксные суммы(минимумы, ...)сортировкитеория чисел
—Войти и решать
Splitting Haybales#90280

Фермер Джон хочет справедливо разделить пакеты сена между его двумя любимыми коровами Беси и Эльза. У него есть \(N\) ( \(1\le N\le 2\cdot 10^5\)) пакетов сена, упорядоченных в невозрастающем порядке. Где \(i\)-ый пакет сена имеет \(a_i\) единиц сена ($2\cdot 10^5\ge a1\ge a2 \ge \dots \ge aN \ge 1$).

ФД хочет разделить непрерывный отрезок пакетов \(a_l, \dots, a_r\) между Беси и Эльзой, рассматривая пакеты в порядке от \(l\) до \(r\), и когда рассматривает \(i\)-ый пакет он даёт его корове, у которой сейчас меньше сена. Если равно - даёт Беси.

Вам даётся \(Q\) (\(1\le Q\le 2\cdot 10^5\)) запросов, каждый описывается тремя целыми числами \(l,r,x\) (\(1\le l\le r\le N\), \(|x|\le 10^9\)). Для каждого запроса, введите на сколько больше единиц сена будет у Беси, после обработки пакетов от \(l\) до \(r\), если Беси начнёт с количеством сена на \(x\) единиц больше чем у Эльзы. Заметим эта величина отрицательна, если вначале у Эльзы будет на \(x\) единиц больше чем у Беси.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит \(N\).

Вторая строка содержит \(a_1\dots a_N\).

Третья строка содержит \(Q\).

Следующие \(Q\) строк содержат \(l, r, x\).

ФОРМАТ ВЫВОДА (на экран / stdout):

Выведите \(Q\) строк, содержащих ответ на каждый запрос.

Префиксные суммы(минимумы, ...)
—Войти и решать
Grass Segments#90276

Беси посадила траву на положительной вещественной прямой. У неё есть \(N\) (\(2\le N\le 2\cdot 10^5\)) различных сортов травы. И она посадит траву \(i\)-го сорта на интервале \([\ell_i, r_i]\) (\(0 < \ell_i < r_i \leq 10^9\)).

Известно, что сорт \(i\) растёт лучше, если есть некоторый сорт \(j\) (\(j\neq i\)) такой, что сорт \(j\) и сорт \(i\) перекрываются на длину не менее \(k_i\) (\(0 < k_i \leq r_i - \ell_i\)). Беси хочет для каждого сорта \(i\) вычислить количество таких of \(j\neq i\), что сорты \(j\) и \(i\) перекрываются на длину не менее \(k_i\).

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит число \(N\).

Каждая из последующих \(N\) строк содержит три разделённых одиночными пробелами целых числа \(\ell_i\), \(r_i\), \(k_i\).

ФОРМАТ ВЫВОДА (на экран / stdout):

Ответы для всех сортов на отдельных строках.

SCORING:

  • Тесты 4-5: \(N \leq 5000\)
  • Тесты 6-11: \(k\) одинаковое для всех интервалов
  • Тесты 12-20: Нет дополнительных ограничений..

В дополнение, в тестах 5, 7, ..., 19, \(r_i \leq 2N\) for all \(i\).

Автор: Benjamin Qi

ОтрезкиПрефиксные суммы(минимумы, ...)Сортировка событий
—Войти и решать
Milk Sum#90233

**Примечание. Ограничение по времени для этой задачи – 4 секунды, что в 2 раза больше, чем по умолчанию.**

\(N\) коров фермера Джона (\(1\le N\le 1,5\cdot 10^5\)) имеют целую продуктивность \(a_1,\dots,a_N\). То есть \(i\)я корова производит \(a_i\) единиц молока за минуту ( \(0 \leq a_i \leq 10^8\)).

Каждое утро фермер Джон начинает с того, что все \(N\) коров подключены к его дойке. От него требуется отцеплять их по одной, отправляя прочь для их ежедневных упражнений. Первая корова, которую он отправляет, снимается с крючка после всего 1 минуты дойки, вторая корова, которую он отправляет, отцепляется после двух минут дойки и так далее. Поскольку первая корова (скажем, корова \(x\)) тратит только одну минуту на доильном аппарате она вносит только \(a_x\) единиц общего количества молока. Вторая корова (скажем, корова \(y\)) тратит на доение всего две минуты и, таким образом, дает \(2a_y\) единиц общего количества молока. Третья корова (скажем, корова \(z\)) приносит всего \(3a_z\) единиц и так далее. Пусть \(T\) представляет собой максимально возможное количество молока, которое может собрать фермер Джон, если он отцепляет своих коров в оптимальном порядке.

Фермеру Джону интересно, как повлияет на \(T\), если часть производительностей молока в его стаде были другими. Для каждого из запросов \(Q\) (\(1\le Q\le 1.5\cdot 10^5\)) каждое из которых задано двумя целыми числами \(i\) и \(j\), пожалуйста, рассчитайте, какой будет новое значение \(T\), если \(a_i\) было установлено в \(j\) (\(0 \leq j \leq 10^8\)). Обратите внимание, что каждый запрос рассматривает временное потенциальное изменение независимо от всех других запросов; то есть \(a_i\) возвращается к исходному значению перед следующим запросом.

ФОРМАТ ВВОДА (ввод поступает с терминала/стандартного ввода):

Первая строка содержит \(N\).

Вторая строка содержит \(a_1\dots a_N\).

Третья строка содержит \(Q\).

Следующие \(Q\) строк содержат по два целых числа \(i\) и \(j\), разделенных пробелом.

ФОРМАТ ВЫВОДА (вывод на терминал / стандартный вывод):

Пожалуйста, выведите значение \(T\) для каждого из запросов \(Q\) в отдельных строках.

Использование сортировкиПрефиксные суммы(минимумы, ...)реализация
—Войти и решать
Haybale Distribution#90191

Фермер Джон развозит сено по ферме.

Ферма имеет \(N\) \((1\le N\le 2\cdot 10^5)\) амбаров, расположенных в целых точках \(x_1,\dots, x_N\) \((0 \le x_i \le 10^6)\) на числовой прямой. ФД запланировал \(N\) перевозок сена в некоторую целую точку \(y\) \((0 \le y \le 10^6)\) и затем одну перевозку к каждому амбару.

К несчастью служба доставки очень расточительна. В частности, для некоторых \(a_i\) и \(b_i\) \((1\le a_i, b_i\le 10^6)\), \(a_i\) пакетов сена теряются на единицу расстояния каждой доставки влево и \(b_i\) пакетов сена теряются на единицу расстояния каждой доставки вправо. Формально при транспортировке из точки \(y\) в амбар в точке \(x\), количество теряемых пакетов сена определяется как

\[\begin{cases} a_i\cdot (y-x) & \text{if } y \ge x \\ b_i\cdot (x-y) & \text{if } x > y \end{cases}.\]

Вам даны \(Q\) \((1\le Q\le 2\cdot 10^5)\) независимых запросов, каждый состоит из возможных значений \((a_i,b_i)\), помогите ФД определить наименьшее количество потерянных пакетов сена, если он выберет \(y\) оптимально.

ФОРМАТ ВВОДА (с клавиатуры):

Первая строка содержит \(N\).

Следующая строка содержит \(x_1\dots x_N\).

Следующая строка содержит \(Q\).

Каждая из последующих \(Q\) строк содержит два целых числа \(a_i\) и \(b_i\).

ФОРМАТ ВЫВОДА (на экран):

Выведите \(Q\) строк, \(i\)-ая строка содержит ответ на \(i\)-ый запрос.

Префиксные суммы(минимумы, ...)
—Войти и решать
Subset Equality#90185

Коровы передают две строки \(s\) и \(t\), каждая с длиной не более \(10^5\), состоящие только из маленьких латинских букв от 'a' до 'r'. Вы должны ответить на \(Q\) запросов (\(1 \leq Q \leq 10^5\)). Для каждого запроса нужно ответить, совпадут ли строки, если в каждой из них оставить только указанные в запросе маленькие латинские буквы (удалив все остальные символы).

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит \(s\).

Вторая строка содержит \(t\).

Третья строка содержит \(Q\).

Каждая из последующих \(Q\) строк содержит строку запроса. В строке запроса символы не повторяются и задаются в алфавитном порядке. Никакой запрос не появляется более одного раза.

ФОРМАТ ВЫВОДА (на экран / stdout):

Для каждого запроса выведите 'Y', если \(s\) и \(t\), с символами только из запроса будут равны и 'N' в противном случае.

Префиксные суммы(минимумы, ...)
—Войти и решать
Counting Liars#90175
Корова Беси прячется где-то на числовой прямой. Каждая из \(N\) (\(1\le N\le 1000\)) других коров Фермера Джона имеет информацию, которой она делится с ФД: \(i\)-ая корова говорит, что Беси прячется в некоторой точке меньше либо равной to \(p_i\), или больше либо равной \(p_i\), (\(0\le p_i\le 10^9\)).

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

ФОРМАТ ВВОДА (С КЛАВИАТУРЫ / stdin):

Первая строка содержит \(N\).

Каждая из следующих \(N\) строк содержит символ L или G, за которым следует целое число \(p_i\). L означает, что \(i\)-ая корова говорит, что Беси скрывается в позиции меньше либо равной \(p_i\), а G означает, что \(i\)-ая корова говорит, что Беси скрывается в позиции больше либо равной \(p_i\)

ФОРМАТ ВЫВОДА (на экран / stdout):

Минимальное количество коров, которые солгали.

Жадный алгоритмЗадачи на моделированиеПрефиксные суммы(минимумы, ...)
—Войти и решать
Sleeping in Class#90158
Беси радовалась введённому индивидуальному обучению. К несчастью её тьютор Фермер Джон очень скучный лектор, и поэтому она часто засыпала во время занятий.

ФД попросил Эльзу записывать количество раз, когда Беси засыпала на каждом занятии. Всего было \(N\) занятий (\(2\le N\le 10^5\)), и Эльза зафиксировала \(a_i\) (\(1\le a_i\le 10^{18}\)) засыпаний на \(i\)-ом занятии. Общее количество засыпаний на всех занятиях не превышает \(10^{18}\).

Эльза хочет представить дело так, что Беси засыпала одинаковое количество раз на каждом занятии.

Единственный способ Эльзы модифицировать свои записи - объединить два соседних занятия или разъединить одно занятие на два. Например, если \(a=[1,2,3,4,5],\) тогда если Эльза объединит второе и третье занятие, то лог станет \([1,5,4,5]\) Если Эльза выберет разделить третье занятие на два, то лог может стать одним из \([1,5,0,4,5]\), \([1,5,1,3,5]\), \([1,5,2,2,5]\), \([1,5,3,1,5]\), or \([1,5,4,0,5]\).

По заданным \(Q\) (\(1\le Q\le 10^5\)) кандидатам \(q_1,\ldots,q_Q\) для наименее любимых Беси чисел (\(1\le q_i\le 10^{18}\)), для каждого из них помогите Эльзе вычислить минимальное количество модификаций лога, чтобы все числа в нём стали одинаковыми.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка каждого теста содержит \(N\), а вторая содержит \(a_1,a_2,\ldots,a_N\). Третья строка содержит \(Q\) - количество запросов, за которым следует \(Q\) строк с целым числом \(q_i\) - кандидат в наименее любимое число Беси.

ФОРМАТ ВЫВОДА (на экран / stdout):

Для каждого \(q_i\) вычислите минимальное количество модификаций, которое требуется для Эльзы, чтобы конвертировать лог в \(q_i\) или выведите \(-1\), если это невозможно.

Жадный алгоритмЗадачи на моделированиеПрефиксные суммы(минимумы, ...)
—Войти и решать
Поделиться
Класснуть