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

Петя и Ваня решили придумать свои правила для игры Дартс. Они взяли круглое игровое поле и поделили его на сектора. Сектора нумеруются натуральными числами. Каждому сектору назначили количество очков, которое можно получить, если попасть дротиком в него. Перед началом игры выбирается нулевой сектор, который служит точкой отсчета: количество очков, которое набирает игрок, попадая в сектор, считается как количество очков, указанное в секторе, умноженное на расстояние (количество секторов) от нулевого сектора. При попадании в нулевой сектор количество очков равно нулю.

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

Определите, какой сектор необходимо выбрать нулевым.


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

Выходные данные
Выведите одно число — номер сектора, который необходимо выбрать как нулевой.
 

Примеры

№	Входные данные	Выходные данные	Примечание
1	6 8 20 5 13 7 19	3	Для данного примера ответ — 3 (5 * 0 + 20 * 1 + 13 * 1 + 8 * 2 + 7 * 2 + 19 * 3 = 120)

В один осенний день чебаркульская сборная по американскому футболу возвращалась на поезде домой после дружеского матча с командой Чебоксар. Подъезжая к очередной реке, главные тренеры футболистов — Алексей Юрьевич и Михаил Леонидович — заметили, что мост через реку на их пути не выглядит слишком надёжно, и, если несколько вагонов с суммарной массой больше W тонн будут целиком находиться на нём, переправа обязательно рухнет. Вагоны, которые находятся на мосту не полностью, не учитываются в суммарной массе.
Алексей Юрьевич, как самый ответственный тренер, точно знает, сколько весит каждый из вагонов поезда: i-й вагон от начала состава имеет массу ai тонн. Михаил Леонидович же имеет идеальное зрение, а потому может сказать, что длина моста равняется длине ровно p вагонов.
Крушения допустить никак нельзя, а потому тренеры приняли волевое решение: отцепить минимальное число вагонов (возможно, все) с конца состава, чтобы поезд смог проехать опасное место. Помогите им и скажите, сколько вагонов придётся оставить до переправы.
Входные данные
В первой строке входных данных через пробел записаны три целых числа n,p и W — количество вагонов в поезде, длина моста в вагонах и максимальная нагрузка в тоннах, которую он выдерживает (1 <= n <= 10⁵, 1 <= p <=10⁵, 0 <= W <=10¹⁴).
Во второй строке через пробел записаны n целых чисел a_i — веса вагонов в порядке их следования от начала состава (1 <= a_i <= 10⁹).
Выходные данные
Выведите единственное число — минимальное количество вагонов, которое надо отцепить от хвоста поезда, чтобы тот смог безопасно проехать по мосту.
 

Примеры

№	Входные данные	Выходные данные
1	4 2 10 5 3 4 8	1

Замечание
В данном тесте мост обрушится, только если на него заедут 3 и 4 вагон одновременно, а это значит, что достаточно отцепить лишь последний вагон.
 

Вы решили съездить проведать своего друга из Озерска. Однако на въезде в город вас остановили и попросили решить задачу, чтобы удостовериться, что вы действительно можете проехать на территорию закрытого города.
Бинарная строка это строка, состоящая только из символов 0 и 1. Полицейский дал вам бинарную строку s₁s₂ ... s_n. Нужно отсортировать эту строку (то есть превратить ее в строку вида 00 ... 0011 ... 11) за наименьшее количество операций. За одну операцию вы можете сделать следующее:
• Выбрать произвольный индекс в строке 1 <= i <= n;
• Для всех j >= i поменять значение в j-й позиции на противоположное, то есть если s_j = 1, то сделать s_j = 0, и наоборот.

Входные данные
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число t (1 <= t <= 10⁴) количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит единственное целое число n (1 <= n <= 10⁵) длину строки.
Вторая строка каждого набора входных данных содержит бинарную строку s длины n.
Гарантируется, что сумма n по всем наборам входных данных не превосходит 2 ·10⁵.

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

Примеры

№	Входные данные	Выходные данные
1	6 1 1 2 10 3 101 4 1100 5 11001 6 100010	0 1 2 1 2 3

Замечание
В первом наборе входных данных строка уже отсортирована.
Во втором наборе входных данных можно выбрать i = 1 и после этого s = 01.
В третьем наборе входных данных можно выбрать i = 1 и получить s = 010, а после этого выбрать i = 2. В результате получим s = 001, то есть отсортированную строку.
В шестом наборе входных данных можно на первой итерации выбрать i = 5 и получить s = 100001. Затем выбрать i = 2 тогда s = 111110. Дальше выбираем i = 1, получая отсор-
тированную строку s = 000001.

У Эвана есть любимое число k и массив a_i длины n. Теперь он просит вас ответить на m запросов.

Для каждого запроса, задаваемого парой чисел l и r, требуется найти количество пар целых чисел i и j таких, что l ≤ i ≤ j ≤ r и xor чисел a_i, a_i + 1, ..., a_j равен k.

Входные данные:
В первой строке даны целые числа n, m и k (1 ≤ n, m ≤ 10⁵, 0 ≤ k ≤ 10⁶) — длина массива, количество запросов и любимое число Эвана соответственно.
Во второй строке записаны n целых чисел ai (0 ≤ a_i ≤ 10⁶) — имеющийся у Эвана массив.
Дальше идут m строк. В i-й строке записаны числа l_i и r_i (1 ≤ l_i ≤ r_i ≤ n), определяющие i-й запрос.

Выходные данные:
Выведите m строк, ответы на запросы в порядке их появления во входных данных.

Примеры:
 

Входные данные	Выходные данные
6 2 3 1 2 1 1 0 3 1 6 3 5	7 0
5 3 1 1 1 1 1 1 1 5 2 4 1 3	9 4 4

Вам даны N целых чисел A1, ..., AN.
На каждый из Q запросов, заданных в формате L R X, выведите количество элементов среди AL, ..., AR, значения которых равны X.

Входные данные
В первой строке задано целое число N (1 <= N <= 2·10⁵). 
Вторая строка содержит N целых чисел Ai (1 <= A_i <= N, 1 <= i <= N). 
В третьей строке задано одно целое число Q (1 <= Q <= 2·10⁵).
Каждая из следующих Q строк содержит три целых числа L, R, X (1 <= L <= R <= N, 1 <= X <= N).

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

Примеры

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

У Макс в блокноте были записаны две строки s длины n и t длины m, состоящие из букв «a» и «b» латинского алфавита. Причем Макс знает, что строка t имеет вид «abab...», то есть на нечетных позициях строки стоит буква «a», а на четных — «b».

Вдруг утром Макс обнаружила, что кто-то испортил ее строку s. Некоторые буквы s были заменены на символ «?».

Назовем последовательность позиций i, i + 1, ..., i + m - 1 вхождением строки t в s, если 1 ≤ i ≤ n - m + 1 и t₁ = s_i, t₂ = s_i + 1, ..., t_m = s_{i + m - 1}.

Красота строки s оценивается как максимальное количество непересекающихся вхождений строки t в нее. Макс может заменить некоторые из символов «?» на «a» или «b» (символы на разных позициях можно заменять на разные буквы). Макс хочет произвести замены так, чтобы красота строки s была максимально возможной. Из всех таких вариантов она хочет заменить как можно меньше символов «?». Найдите, сколько замен она должна сделать.

Входные данные:
Первая строка содержит одно целое число n (1 ≤ n ≤ 10⁵) — длину строки s.
Вторая строка входных данных содержит строку s длины n, состоящую только из букв «a» и «b» латинского алфавита, а также символов «?».
Третья строка содержит целое число m (1 ≤ m ≤ 10⁵) — длину строки t. Сама строка t содержит «a» на нечетных позициях, и «b» на четных.

Выходные данные:
Выведите единственное целое число — минимальное количество замен, которое должен сделать Вася, чтобы сделать красоту строки s максимально возможной.

Примеры:
 

Входные данные	Выходные данные
5 bb?a? 1	2
9 ab??ab??? 3	2

Пояснения:
В первом примере строка t имеет вид «a». Единственный оптимальный вариант — заменить все символы «?» на «a».
Во втором примере используя две замены можно получить строку «aba?aba??». Больше двух вхождений получить нельзя.

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

Для успешного налаживания контактов с аборигенами руководитель группы планирует делать подарок вождю каждого встреченного племени. С этой целью он привёз длинную цепочку из стекляшек, похожих на драгоценные камни. 
Представим цепочку как строку s, состоящую из маленьких букв английского алфавита, где каждая буква означает тип кусочка стекла на соответствующей позиции. 
Исследователи собираются разрезать цепочку на некоторые фрагменты, после чего вручать ровно один фрагмент вождю каждого встреченного группой племени. Руководитель исследователей решил разделить цепочку на фрагменты согласно следующим правилами:

• Чтобы не тратить на разрезания много времени, каждый фрагмент должен являться группой соседних стекляшек цепочки, то есть подстрокой строки s.
• Все стекляшки должны быть использованы, то есть каждая стекляшка должна оказаться включённой ровно в один фрагмент.
• Поскольку исследователи не знают, как аборигены оценят те или иные виды стекляшек, они хотят, чтобы каждому вождю достался один и тот же набор стекляшек без учёта порядка. Иными словами, для любого типа стекляшек количество стекляшек этого типа должно быть одинаковым в каждом из фрагментов.
• Исследователи не знают, сколько племён обитает на острове, поэтому количество подготовленных фрагментов должно быть максимальным.

Помогите руководителю определить максимальное количество фрагментов, которое может получиться.

Входные данные:
В первой строке дана строка s (1 <= |s| <= 5000000).

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

Примеры:
 

Входные данные	Выходные данные
abbabbbab	3
aabb	1

Пояснения:
В первом примере исследователи могут разбить цепочку 'abbabbbab' на фрагменты 'abb', 'abb', 'bab', тогда вождю каждого встреченного ими племени достанется по одной стекляшке типа 'a' и по две стекляшки типа 'b'.

Во втором примере строку невозможно поделить цепочку больше чем на один фрагмент, соблюдая все условия.

У Гекльберри Финна есть две строки s и t одинаковой длины n.
Гекльберри Финну нравится, когда у строк одинаковые префиксы (начала), поэтому он может поменять местами два символа в строке s, чтобы общий префикс строк s и t стал больше.
Однако этот трюк довольно утомительный, поэтому Гекльберри Финн либо совсем не будет его делать, либо сделает ровно один раз.

Помогите Гекльберри Финну определить наибольшую длину общего префикса строк s и t, которую он может получить.


Входные данные:
В первой строке дано натуральное число n (1 <= n <= 200000) - длина строк s и t
Во второй строке дана строка s, состоящая из строчных латинских букв.
В третьей строке дана строка t, состоящая из строчных латинских букв.

Выходные данные:
Выведите одно натуральное число - наибольшую длину общего префикса s и t, которую можно получить, применив операцию обмена двух символов в строке s не более одного раза.

Примеры:
 

Входные данные	Выходные данные
3 wai add	1
5 qdyid xreac	0

Том Сойер и Гекльберри Финн вместе читают вслух вырезку из газеты. Но получилось так, что Том Сойер начал читать с i-ого символа, а Гекльберри Финн с j-ого. 
Сколько букв они смогут прочитать, прежде чем обнаружат, что начали читать с разных мест или пока оба не дочитают до конца?

Входные данные:
В первой строке дана строка S (1 <= |S| <= 10⁵), состоящая из строчных латинских букв - надпись из газетной вырезки.
В следующей строке дано натуральное число q - количество запросов.
В следующих q строках дано по два натуральных числа i и j - позиции, с которых начинают читать Том Сойер и Гекльберри Финн соответственно.

Выходные данные:
Выведите q строк, в каждой из которых должно быть одно целое число - количество символов, совпадающих при чтении подстрок, начинающихся с i-ого и j-ого символа.

Примеры:
 

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

Во время покраски забора Том Сойер написал на нем слово s. Однако затем он решил, что слова-палиндромы смотрятся красивее.
Теперь он хочет дописать к имеющемуся слову s справа другое слово g так, чтобы получившееся слово sg было палиндромом. Однако в целях экономии краски длина g должна быть как можно меньше.
Помогите Тому Сойеру определить слово g.

Входные данные:
В первой строке дано слово s (1 <= |s| <= 200000), состоящее из строчных латинских букв.

Выходные данные:
Выведите минимально возможное по длине слово g, которое нужно дописать, чтобы слово sg на заборе стало палиндромом. Если дописывать ничего не надо, то выведите '-'.

Примеры:
 

Входные данные	Выходные данные
abc	ba
a	-

Дана строка S = s₁s₂...s_n и множество запросов вида (l₁, r₁, l₂, r₂). Для каждого запроса требуется ответить, равны ли подстроки s_l1...s_r1 и s_l2...s_r2.


Входные данные:
В первой строке дана строка S (1 <= |S| <= 10⁵), состоящая из строчных латинских букв. 
Во второй строке дано натуральное число q (1 <= q <= 10⁵) - количество запросов.
В следующих q строках дано по 4 натуральных числа - l₁, r₁, l₂, r₂ (1 <= l₁ <= r₁ <= |S|, 1 <=l₂ <= r₂ <= |S|).

Выходные данные:
Для каждого запроса выведите '+', если подстроки равны, и '-', в противном случае.

Примеры:
 

Входные данные	Выходные данные
abacaba 4 1 1 7 7 1 3 5 7 3 4 4 5 1 7 1 7	++-+

Беси недавно получила набор красок, и она хочет разрисовать длинную изгородь с одной стороны её пастбища. Изгородь состоит из N последовательных 1-метровых сегментов (1≤N≤10⁵). У Беси есть краски 26 различных цветов, которые она пометила буквами от 'A' до Z' в порядке возрастания темноты ('A' - самый светлый цвет, 'Z' - самый тёмный). Поэтому она может описывать раскраску изгороди как строку из N символов (где каждый символ один из - от 'A' до Z').
Изначально все сегменты изгороди не раскрашены. Беси может раскрасить любой непрерывный диапазон сегментов одним цветом за одно прикосновение кисти, также она никогда не красит более светлым поверх более темного (она может красить более темным поверх более светлого).

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

.... -> BBB. -> BBLL -> BQQL
Ограниченная во времени, Беси может оставить некоторые последовательные отрезки не покрашенными. Сейчас она рассматривает Q кандидатов отрезков (1≤Q≤10⁵), каждый задаётся двумя целыми числами (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

Дана последовательность из N чисел. Рассматриваются все её непрерывные подпоследовательности, которые содержат кратное K количество отрицательных чисел, заканчивающихся цифрой m. Найдите среди них подпоследовательность с максимальной суммой.  Программа должна вывести одно число – максимальную сумму элементов такой подпоследовательности. Гарантируется, что в исходной последовательности существует хотя бы K отрицательных чисел, заканчивающихся цифрой m.


Входные данные
В первой строке программа получается три числа: количество чисел в последовательности N (100 <= N <= 5000000), натуральное число K и натуральное число m (0 <= m <= 9). В каждой из следующих N строк записано одно целое число, не превышающее по модулю 10000. Гарантируется, что сумма любой подпоследовательности исходной последовательности не превышает по модулю 10⁹.

Выходные данные
Выведите на экран ответ на задачу.
 
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1

 

Дана последовательность из N чисел. Рассматриваются все её непрерывные подпоследовательности, которые содержат ровно K отрицательных чисел, заканчивающихся цифрой m. Найдите среди них подпоследовательность с максимальной суммой.  Программа должна вывести одно число – максимальную сумму элементов такой подпоследовательности. Гарантируется, что в исходной последовательности существует хотя бы K отрицательных чисел, заканчивающихся цифрой m.

Входные данные
В первой строке программа получается три числа: количество чисел в последовательности N (100 <= N <= 5000000), натуральное число K и целое число m (0 <= m <= 9). В каждой из следующих N строк записано одно целое число, не превышающее по модулю 10000. Гарантируется, что сумма любой подпоследовательности исходной последовательности не превышает по модулю 10⁹.

Выходные данные
Выведите на экран ответ на задачу.
 
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	8 2 3 6 -3 -2 4 -1 -13 8 13	12	Нужные нам числа -3 и -13. Вся исходная последовательность даст максимальную сумму элементов.

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

Входные данные
В первой строке записаны натуральные числа N (1 <= N <= 10⁸) и K (1 <= K <= 100 ). Каждая из следующих N строк содержит одно натуральное число, не превышающих 10000.

Выходные данные
Выведите на экран одно число – количество таких подпоследовательностей. 

Примеры

№	Входные данные	Выходные данные
1	5 3 33 41 19 22 40	4

Дана последовательность из N чисел. Рассматриваются все её непрерывные подпоследовательности, в которых количество отрицательных чисел не превышает С. Найдите среди них подпоследовательность с максимальной суммой, длины L. В ответе укажите сумму найденной подпоследовательности.

Входные данные
В первой строке записаны 3 числа: количество чисел N (1 <= N <= 1 000 000),  L и C (\(1 <= L, C <= N <= 1 000 000\)). Каждая из следующих N строк содержит одно число, не превышающее по модулю 1 000.

Пример организации исходных данных во входном файле (для L = 3 и С = 3):
5 3 3
1
-1
2
-2
3

В этом наборе можно выбрать несколько последовательностей, но с максимальной суммой равной 3 будет: 2+(-2)+3. 
Ответ (для С = 3 и L = 3): 3. 

 

Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна K. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.

Входные данные
В первой строке записаны натуральные числа N (1 <= N <= 10⁸) и K (1 <= K <= 100 ). Каждая из следующих N строк содержит одно натуральное число, не превышающих 10000.

Выходные данные
Выведите на экран одно число - количество элементов самой короткой подпоследовательности с максимальной суммой элементов кратной К.
 
 

Примеры

№	Входные данные	Выходные данные
1	7 43 21 13 9 19 17 26 95	2

В этом наборе можно выбрать последовательности 21+13+9 (сумма 43) и 17+26 (сумма 43). Самая короткая из них, 17 + 26, имеет длину 2. Для указанных программа должна вывести число 2.

Дана последовательность из N чисел. Найдите минимальную сумму всех элементов собственного префикса последовательности, у которого сумма всех элементов префикса при делении на K имеет тот же остаток, что и сумма всех элементов данной последовательности.  Если таких префиксов несколько определите тот, у которого меньше длина. Выведите на экран длину такого префикса. Гарантируется, что такой префикс существует.


Входные данные
В первой строке записаны два числа: количество чисел в последовательности N (1 <= N <= 10⁸) и число K (1 <= K <= 100). Далее идет N строк, по одному целому числу в строке. Каждое число не превышает 10000.

Выходные данные
Выведите на экран ответ на задачу.
 
 

Примеры

№	Входные данные	Выходные данные
1	5 2 2 -2 2 -2 2	2

 

 

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


Входные данные
В первой строке записаны два числа: количество чисел в последовательности N (1 <= N <= 10⁸) и число K (1 <= K <= 100). Далее идет N строк, по одному натуральному числу в строке. Каждое число не превышает 10000.

Выходные данные
Выведите на экран ответ на задачу.
 

Примеры

№	Входные данные	Выходные данные
1	5 3 33 41 18 23 40	92

 
 

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

Входные данные
В первой строке записаны два числа: количество чисел в последовательности N (1 <= N <= 10⁸) и число K (1 <= K <= 100). Далее идет N строк, по одному натуральному числу в строке. Каждое число не превышает 10000.

Выходные данные
Выведите на экран ответ на задачу.
 

Примеры

№	Входные данные	Выходные данные
1	5 3 33 41 18 23 40	2