Линейные структуры

165 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Нет времени рисовать#39574
Беси недавно получила набор красок, и она хочет разрисовать длинную изгородь с одной стороны её пастбища. Изгородь состоит из N последовательных 1-метровых сегментов (1≤N≤105). У Беси есть краски 26 различных цветов, которые она пометила буквами от 'A' до Z' в порядке возрастания темноты ('A' - самый светлый цвет, 'Z' - самый тёмный). Поэтому она может описывать раскраску изгороди как строку из N символов (где каждый символ один из - от 'A' до Z').
Изначально все сегменты изгороди не раскрашены. Беси может раскрасить любой непрерывный диапазон сегментов одним цветом за одно прикосновение кисти, также она никогда не красит более светлым поверх более темного (она может красить более темным поверх более светлого).

Например, изначально не покрашенный отрезок длины 4 она может покрасить так:

.... -> BBB. -> BBLL -> BQQL
Ограниченная во времени, Беси может оставить некоторые последовательные отрезки не покрашенными. Сейчас она рассматривает Q кандидатов отрезков (1≤Q≤105), каждый задаётся двумя целыми числами (a,b) (1≤a≤b≤N), указывающих индексы конечных точек отрезка, которые должны остаться не раскрашенными.

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

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

Каждая из следующих Q строк содержит два разделённых пробелом целых числа a и b представляющих диапазон сегментов, которые возможно останутся не раскрашенными.

Выходные данные
Для каждого из Q кандидатов выведите ответ на новой строке.
Примеры
№ Входные данные Выходные данные Пояснение
1 
8 2
ABBAABCB
3 6
1 4
 4
3		 В этом примере, исключение диапазона соответствует желаемому образцу В этом примере исключение диапазона BAAB требует четыре прикосновения для раскраски, а исключение диапазона ABBA - только три.

.... -> AA.. -> ABBB -> ABCB
Префиксные суммы(минимумы, ...)Стек
✓ 2✗ 6900средняяВойти и решать
Modern Art 2#27219
Picowso решила переключиться на 1-мерный стиль.
Теперь её картины могут описываться 1-мерным массивом цветов длины NN (1≤N≤100,000). А вот стиль у неё остался прежний: Он начинает на пустом отрезке и рисует отрезками. Она использует каждый из цветов 1…N ровно один раз, хотя некоторые из цветов могут быть полностью скрыты к концу рисования.
 
Moonet, соперник Picowso, придумал, как копировать картины Picowso. Он рисует множество не соединяющихся интервалов и т.д. Moonet может рисовать не более одного интервала каждого цвета во время всего процесса. Вычислите количество таких раундов, которые требуются Moonet, чтобы скопировать 1-мерную картину Picowso.
 
ФОРМАТ ВВОДА:
 
Первая строка ввода содержит N, и следующие N строк содержат целое число в интервале 0…N, указывающее цвет каждой ячейки на 1-мерном холсте (0 для пустой ячейки).

ФОРМАТ ВЫВОДА:
 
Выведите минимальное количество раундов, которое требуется для копирования заданного рисунка или -1, если невозможно повторить этот рисунок стилем, аутеничным стилю Picowso (то есть, её нельзя нарисовать слоями последовательностей интервалов, по одному каждого цвета).
 
Ввод Вывод
7
0
1
4
5
1
3
3
 2

Примечание
В данном примере интервал цвета 1 должен быть закрашен в более раннем раунде, чем интервалы цветов 4 и 5, поэтому необходимо как минимум два раунда.
 
КонструктивЛинейные структурыСтек
✓ 2✗ 81 000средняяВойти и решать
Двумерный дождь#27041
Игра PitCraft происходит в двумерном мире, который состоит из блоков размером 1 на 1 метр.
Остров игрока представляет собой набор столбцов различной высоты, состоящих из блоков камня и окруженный морем.
Над островом прошёл сильный дождь, который заполнил водой все низины, а не поместившаяся в них вода стекла в море, не увеличив его уровень. По ландшафту острова определите, сколько блоков воды осталось после дождя в низинах на острове.
 
Формат входных данных
В первой строке записано натуральное число N (0 <= N <= 100 000)  количество столбцов, задающих ландшафт острова.
Во второй строке записано N натуральных чисел Hi (1 <= Hi <= 109)  высоты столбцов.
 
Формат выходных данных
Выведите одно число  количество блоков занятых водой.
Система оценки
Решения, верно работающие при N <= 100, будут набирать не менее половины баллов.
 
Ввод Вывод
11
2 5 2 3 6 9 3 1 3 4 6		 18
 
Замечание
Пример соответствует рисунку. Черным цветом обозначен камень, серым  вода.

Линейные структурыПрефиксные суммы(минимумы, ...)
✓ 52✗ 209700средняяВойти и решать
Выбросы#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средняяВойти и решать
Склеивание верёвок#93187

На столе лежит n верёвок разной длины. Вам нужно связать их все в одну длинную верёвку. За одну операцию можно взять любые две верёвки и связать их в одну — стоимость такой операции равна сумме длин этих двух верёвок.

Например, если связать верёвки длиной 3 и 5, получится одна верёвка длиной 8, а стоимость операции — 8. Эту новую верёвку можно затем связывать с другими.

Требуется найти минимальную суммарную стоимость, за которую можно связать все n верёвок в одну.
 

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

В первой строке записано натуральное число n (1 ≤ n ≤ 50 000) — количество верёвок.

Во второй строке через пробел записаны n натуральных чисел a1, a2, …, an (1 ≤ ai ≤ 10 000) — длины верёвок.
 

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

Выведите одно целое число — минимальную суммарную стоимость связывания всех верёвок в одну. Если верёвка одна (n = 1), выведите 0.

Внимание: ответ может не помещаться в 32-битный целочисленный тип. В языке C++ используйте тип long long; в Python ограничений нет.
 

Пояснение к первому примеру

Оптимальная последовательность: связываем 2 и 3 (стоимость 5), получаем набор {4, 5, 6}. Связываем 4 и 5 (стоимость 9), получаем {6, 9}. Связываем 6 и 9 (стоимость 15). Итого: 5 + 9 + 15 = 29.

Дек
—Войти и решать
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):

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

Жадный алгоритмПрефиксные суммы(минимумы, ...)
—Войти и решать
Censoring (Bronze)#90403

Фермер Джон купил подписку журнала Good Hooveskeeping для своих коров, теперь им есть что почитать. К несчастью, последний номер содержит довольно неподходящую статью, как приготовить совершенный бифштекс. ФД хочет чтобы его коровы не увидели эту статью.

ФД взял текст из журнала и создал строку S длиной не более чем 10^6 символов. Из неё он хочет удалить все вхождения подстроки T длиной <= 100 символов неподходящего содержания. Чтобы сделать это, ФД ищет первое вхождение T в S и удаляет его. Затем он повторяет процесс опять, снова удаляя первое вхождение T, продолжая так до тех пор, пока больше не станет вхождений T в S. Заметим, что удаление одного вхождения может создать другое вхождение, которое не существовало раньше.

Пожалуйста, помогите ФД определить конечное содержание строки S после завершения всех удалений.

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

Первая строка содержит S. Вторая строка будет содержать T. Длина T не более чем длина S, и все символы S и T - маленькие латинские буквы (a..z).

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

Строка S после завершения всех удалений. Гарантируется, что S не станет пустой после завершения процесса всех удалений.

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

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

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

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

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

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

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

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

Задачи на моделированиеПрефиксные суммы(минимумы, ...)
—Войти и решать
Cow Dance Show#90399
После нескольких месяцев репетиций, коровы готовы дать ежегодное танцевальное представление - балет "Cowpelia".

Остался непрояснённым только размер сцены. Сцена размера \(K\) может выдержать \(K\) коров, танцующих одновременно. \(N\) коров в стаде (\(1 \leq N \leq 10,000\)) пронумерованы последовательно \(1 \ldots N\) в порядке, в котором они должны появиться на сцене во время танца. Каждая корова \(i\) планирует танцевать определённое время \(d(i)\). Изначально коровы \(1 \ldots K\) появляются на сцене и начинают танцевать. Когда первая из этих коров завершит свой танец, она покидает сцену и корова \(K+1\) немедленно начинает танцевать и т.д. Поэтому всегда \(K\) коров танцуют, за исключением последнего отрезка шоу, когда коровы уходят, но не добавляются. Шоу завершается, когда последняя корова завершит свой танец в момент времени \(T\).

Понятно, что чем больше значение \(K\), тем меньше время \(T\). Поскольку шоу не может длится очень долго, вам на вводе даётся верхняя граница \(T_{max}\), указывающая максимально возможное значение величины \(T\). Ваша задача - определить минимально возможное подходящее значение \(K\).

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

Первая строка ввода содержит \(N\) и \(T_{max}\), где \(T_{max}\) - целое число, не более 1 000 000.

Следующие \(N\) строк задают длительности танцев \(d(1) \ldots d(N)\) для коров \(1 \ldots N\). Каждое из \(d(i)\) - целое число в интервале \(1 \ldots 100,000\).

Гарантируется, что если \(K=N\), шоу закончится вовремя.

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

Выведите наименьшее возможное значение \(K\) такое, что танцевальное шоу закончится не более чем через \(T_{max}\) единиц времени.

Бинарный поиск по ответуЖадный алгоритмОчередь
—Войти и решать
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\) строк, содержащих ответ на каждый запрос.

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