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

ID 30659. Сумма на отрезке

Примеры

ID 29638. Тихий Дон №3

ID 29640. Тихий дон №2

Аксинья любит Григория, но она замужем за Степаном. Со своим мужем она несчастна, поэтому время, которое она проводит с ним можно характеризовать отрицательным показателем счастья Аксиньи (\(a_i < 0\)), а то время, которое она проводит с Григорием, - положительным показателем счастья (\(a_i > 0\)). Известно, что Аксинья проводит один день либо с мужем, либо с Григорием. 

Примеры

ID 29655. Рубка деревьев

ID 30699. Банды Фомина №2

Банда Фомина состоит из n групп, в каждой из которых ai человек. Планируется провести q рейдов. В i-ом рейде будет участвовать ровно один разбойник из каждой группы, номер которой лежит в отрезке \([l_i, r_i]\).

Примеры

ID 30691. Банды Фомина

ID 33256. Кот Гусь и случайная матрица

Примеры

ID 38139. Достаточно зеленого

Пастбище Фермера Джона может рассматриваться как NхN решётка (\(1<=N<=500\)) квадратных ячеек с травой (как большая шахматная доска). Из-за изменчивости почвы, трава в некоторых ячейках зеленее, чем в других. Каждая ячейка (i,j) описывается целым числом - уровнем зелёности G(i,j), в интервале \(1…200\).

Фермер Джон хочет сделать фотографию прямоугольной подрешётки своего пастбища. Он хочет, чтобы минимальная из величин G на его фотографии была ровна 100. Помогите ему посчитать, сколько таких различных фотографий он сможет сделать. Подрешётка может быть размером от всего пастбища и до одной ячейки. Всего существует \(N^2(N+1)^2/4\) различных подрешёток, для хранения такого числа используйте 64-битное целое (типа long long в C++).

Заметим, что для ответа требуется использовать 64-битную целую переменную типа long long в C++.

Примеры

ID 38384. Выбор цветов для букета

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

Придя в цветочный магазин, Володя обнаружил, что букет можно составлять из цветов m различных видов, причём количество цветов каждого вида не ограничено. Володя знает, что от первого цветка i-го вида в букете его супруга становится счастливее на a_i, а от каждого следующего цветка  
такого вида она становится счастливее на b_i. То есть, если в букете x_i > 0 цветов вида i, то от цветов этого вида жена Володи становится счастливее на a_i + (x_i − 1) · b_i.

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

Формат входных данных
В первой строке вводятся два целых числа n и m (1 ≤ n ≤ 10⁹ , 1 ≤ m ≤ 100 000) — требуемое 
количество цветов в букете и количество доступных видов цветов.
Каждая из следующих m строк описывает i-й вид цветов и содержит два целых числа a_i и b_i (0 ≤ a_i , b_i ≤ 10⁹ ) — увеличение счастья от первого цветка i-го вида и увеличение счастья от каждого последующего цветка этого вида.

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

Примеры

ID 38589. Практический тест

У нас есть сетка с H строками и W столбцами. Квадрат в i-й строке и j-м столбце будет называться Square(i, j). Целые числа от 1 до H·W записаны по всей сетке, а целое число, записанное в Square(i, j), равно Ai,j.
Вы - волшебник (волшебница), и можете телепортировать фигуру, помещенную на Square(i, j) в Square(x, y), потратив \(|x-i|+|y-j|\) маджиков (магических монет).
Теперь вам нужно пройти Q практических тестов на свои способности как волшебника (волшебницы). I-е испытание будет проводиться следующим образом:
- первоначально фигура располагается в квадрате, где записано целое число Li;
- пусть x будет целым числом, записанным в квадрате, занятом фигурой. Неоднократно переместите фигуру в квадрат, где написано целое число x+D, пока x не станет равен Ri. Тест заканчивается, когда x = Ri .
Гарантируется, что Ri- Li делится на D.
Для каждого теста найдите сумму маджиков, израсходованных во время этого теста.

Входные данные
В первой строке заданы три целых числа: H, W и D (\(1\leq H,W \leq 300\), \(1 \leq D \leq H \cdot W\)).
В следующих H строках записано по W чисел Ai,j (\(1 \leq A_{i,j} \leq H \cdot W\), \(A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))\).
В следующей строке записано целое число Q (\(1 \leq Q \leq 10^5\)).
В последних Q строках записано по 2 целых числа: Li и Ri (\(1 \leq L_i \leq R_i \leq H \cdot W\)), \((R_i-L_i)\) кратно D.

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

Примеры

ID 39110. Длина подстроки

У вас есть строка s. Вы хотите сделать новую строку, записывая в ней каждую букву количество раз равное порядковому номеру этой буквы в алфавите. Например, s = "abcdc", новая строка s_new = "abbcccddddccc".  Нам стало интересно, какая получится у вас длина строки, если выписать все символы исходной строки, начиная с символа l и заканчивая символом r. Всего у нас k запросов к вам.


Входные данные
В первой строке программа получает на вход два числа n и k (1<=n<=10⁶, 1<=k<=10⁶), где n - длина строки, k - количество запросов. Во второй строке записана строка s длиной n. В следующих k строках расположены границы отрезков l и r (1 <= l <= r <= n). l, r - порядковые номера символов в строке, начиная с 1.

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

Примеры

ID 39356. Получите OK

Дана строка S длины N, состоящая из символов S, T, O и K. Дайте ответ на Q запросов следующего вида.
Запрос i(1 <= i <= Q): для заданных целых чисел li и ri (1 <= l_i< r_i <= N),  рассматривается подстрока S, начинающаяся с индекса li и заканчивающася индексом ri (оба включительно). Необходимо определить, сколько раз в этой строке втречается OK как подстрока?
 

Пояснение

Примеры

ID 39381. Гармоничная последовательность

Цикл лекций в университете Флатландии посвящен изучению последовательностей.

Профессор называет последовательность целых чисел \(a_1, a_2, ..., a_n\) гармоничной, если каждое число, кроме \(a_1\) и \(a_n\), равно сумме соседних: \(a_2 = a_1 + a_3, a_3=a_2+a_4, ..., a_{n-1}=a_{n-2}+a_n\). Например, последовательность [1,2,1,–1]  является гармоничной, поскольку 2=1+1, и 1=2+(–1) .

Рассмотрим последовательности равной длины: \(A=[a_1,a_2, ... a_n]\)   и \(B=[b_1,b_2, ... b_n]\). Расстоянием между этими последовательностями будем называть величину \(d(A,B)= |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|\) . Например, \(d([1,2,1,–1][1,2,0,0])=|1–1|+|2–2|++|1–0|+|–1–0|=0+0+1+1=2 \)

В конце лекции профессор написал на доске последовательность из n целых чисел \(B=[b_1,b_2, ... b_n]\)и попросил студентов в качестве домашнего задания найти гармоничную последовательность \(A=[a_1,a_2, ... a_n]\), такую, что \(d(A, B)\) минимально. Чтобы облегчить себе проверку, профессор просит написать в качестве ответа только искомое минимальное расстояние \(d(A,B)\) .

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

Входные данные
Первая строка входного файла содержит целое число n – количество элементов в последовательности ( \(3 \le n \le 300 000\)).

Вторая строка содержит n целых чисел \(b_1, b_2, …, b_n (–10^9 \le b_i \le 10^9 )\) .

Выходные данные
Выходной файл должна содержать одно целое число: минимальное возможное расстояние от последовательности во входном файле до гармоничной последовательности.

Примеры

ID 39482. Подпоследовательность длиной L

Дана последовательность из 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. 

 

ID 39574. Нет времени рисовать

Беси недавно получила набор красок, и она хочет разрисовать длинную изгородь с одной стороны её пастбища. Изгородь состоит из 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 кандидатов выведите ответ на новой строке.

Примеры

8 2
ABBAABCB
3 6
1 4

ID 39671. Подстроки в строке

Дана строка 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|).

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

Примеры:
 

ID 39672. Том Сойер и слово на заборе

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

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

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

Примеры:
 

ID 39673. Чтение вслух

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

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

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

Примеры:
 

ID 39674. Гекльберри Финн и две строки

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

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


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

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

Примеры:
 

ID 39675. Культурный контакт

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

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

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

ID 39964. Максимальные вопросы

У Макс в блокноте были записаны две строки 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 максимально возможной.

Примеры:
 

ID 41228. XOR и любимое число

У Эвана есть любимое число 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 строк, ответы на запросы в порядке их появления во входных данных.

Примеры:
 

ID 42853. Отрезок с максимальной суммой

В одномерном массиве, заполненном произвольными целыми числами, за один проход найдите непрерывный кусок, сумма чисел в котором максимальна.
Примечание. Фактически требуется найти такие i и j (i≤j), что сумма всех элементов массива от a_i до a_j включительно будет максимальна.

5
-1
2
3
-2
2

2
3

7
2
-2
3
-1
5
-2
7

3
7

ID 42852. Сумма подряд идущих

Дан массив целых чисел a[1], a[2], ..., a[n] и натуральные числа k и m. 
Укажите минимальное значение i, для которого a[i] + a[i+1] + ... + a[i + k] = m (то есть сумма k + 1 подряд идущих элементов массива равна m). 
Если такого значения нет, то выведите 0. Вложенные циклы и дополнительные массивы не использовать (требуется решить задачу за один проход исходного массива).

4 1 22
9 13 10 -11 

1

ID 42851. Торговля акциями

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

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

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

Кроме этого, будем считать, что продажа и покупка будет осуществляться только с акциями одного типа. На начало этого периода вы располагаете суммой в x рублей. Для каждого из дней известна цена a_i (от ask — цена предложения), по которой можно купить одну акцию, и цена b_i (от bid — цена спроса), по которой можно одну акцию продать. При этом в соответствии с действующими правилами торгов на бирже разрешается продавать и покупать только целое число акций (например, если у вас есть 5 рублей, а акция стоит 2 рубля, то вы можете купить не более двух акций).

Требуется написать программу, которая по имеющимся данным о стоимости акций в каждый из дней, найдет оптимальную стратегию покупки и продажи акций.

Если существует несколько вариантов оптимальной стратегии, то выведите любой из них

5 1000
2 3 1 4 3
1 2 1 2 3

5 1000
10 9 8 7 6
9 8 7 6 5

ID 42850. Клиппи и Мерлин грабят банк

Клиппи и Мерлин решили грабить банк «Документы», который представляет из себя N расположенных в ряд банковских ячеек, пронумерованных последовательно числами от 1 до N .

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

Чтобы не вызывать лишних подозрений, Клиппи и Мерлин решили ограбить всего две ячейки "— по одной на каждого. Также, чтобы охрана банка не почуяла неладного, они решили работать далеко друг от друга "— между ними должно быть не меньше K банковских ячеек.

Входные данные
В первой строке вводятся два числа "— N ( 2 ≤ N ≤ 10 ⁵ ) и K ( 0 ≤ K < N - 1 ) соответственно. В второй строке вводятся N чисел a _i ( 0 ≤ a _i ≤ 10 ⁹ ) "— стоимости хранимых ценностей в ячейках от 1 до N соответственно.

Выходные данные
Выведите два числа в возрастающем порядке "— номера ячеек, которые нужно ограбить, чтобы суммарно украсть как можно более дорогие ценности, не вызвав при этом лишних подозрений. Если вариантов несколько выберите тот, в котором меньший номер вскрываемой ячейки был как можно ближе к единице, чтобы в экстренном случае покинуть банк как можно скорее. Если и таких вариантов несколько, выберите тот, в котором и больший номер вскрываемой ячейки был как можно меньше.

Примеры

6 2
2 4 3 1 4 4

2 5

ID 43124. Бинарная сортировка

Вы решили съездить проведать своего друга из Озерска. Однако на въезде в город вас остановили и попросили решить задачу, чтобы удостовериться, что вы действительно можете проехать на территорию закрытого города.
Бинарная строка это строка, состоящая только из символов 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⁵.

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

Примеры

ID 43720. Дартс

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

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

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


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

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

Примеры

ID 43721. Два мусоровоза

На каждом километре кольцевой автодороги с двусторонним движением установлены контейнеры для мусора. Длина кольцевой автодороги равна N километров. Нулевой километр и N-й километр автодороги находятся в одной точке. Известно количество мусора, которое накапливается ежедневно в каждом из контейнеров.
На автодороге работают два мусоровоза. Один едет по часовой стрелке, другой против. Оба мусоровоза выезжают из центра переработки одновременно навстречу друг другу и встречаются возле одного из контейнеров. Из одного контейнера вывезти мусор может только один мусоровоз. Время доставки мусора вычисляется как произведение количества мусора на расстояние от пункта до центра переработки. Центр переработки отходов открыли в одном из пунктов сбора мусора таким образом, чтобы общее время сбора мусора двумя мусоровозами было минимально.
Определите, возле контейнера с каким номером необходимо поставить центр переработки, чтобы потребовалось минимальное время мусоровозам для сбора мусора.

Входные данные
Первая строка входных данных содержит число N (1 <= N <= 10 000 000) – количество пунктов сбора мусора на кольцевой автодороге. В каждой из следующих N строк находится число – количество мусора в контейнере (все числа натуральные, количество мусора в каждом пункте не превышает 1000). Числа указаны в порядке расположения контейнеров на автомагистрали, начиная с первого километра.

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

Примеры

ID 43722. Непрерывная подпоследовательность

Дана последовательность из N натуральных чисел. Известно, что сумма всех чисел последовательности не превышает 10⁹. Рассматриваются все её непрерывные подпоследовательности, в которых количество нечётных чисел кратно K = 7. Найдите наибольшую сумму такой подпоследовательности. 

Входные данные
Первая строка входных данных содержит одно число N (1 <= N <= 1 000 000) -  количество чисел. Каждая из следующих N строк содержит одно натуральное число, не превышающее 1 000.
 
Входные данные
Выведите ответ на задачу

ID 21887. Призы

Алиса и Боб стали победителями телевикторины, и теперь им предстоит выбрать себе призы. На выбор предлагается n призов, пронумерованных от 1 до n.
Распределение призов происходит следующим образом. Организаторы телевикторины сообщают победителям целое положительное число k (1 ≤ k ≤ n / 3). Сначала Алиса выбирает себе любые k подряд идущих номеров призов. Потом Боб выбирает себе k подряд идущих номеров призов, при этом он не может выбирать номера, которые уже выбрала Алиса. После этого победители забирают выбранные ими призы.
Алиса хорошо знает Боба, и для каждого приза выяснила его ценность для Боба, которая является целым положительным числом. Алиса обижена на Боба и хочет выбрать свои призы так, чтобы суммарная ценность призов, которые достанутся Бобу, была как можно меньше. При этом Алису не волнует, какие призы достанутся ей.

Требуется написать программу, которая по информации о ценности призов и значению k определит, для какого минимального значения x Алиса сможет добиться того, чтобы Боб не смог выбрать призы с суммарной ценностью больше x.

Формат входного файла
Первая строка входного файла содержит два целых числа: n — общее количество призов и k — количество подряд идущих номеров призов, которое должен выбрать каждый из победителей (3 ≤ n ≤ 100 000, 1 ≤ k ≤ n / 3). Вторая строка содержит n целых положительных чисел: a1, a2, …, an. Для каждого приза указана его ценность для Боба (1 ≤ ai ≤ 10⁹ ).

Формат выходного файла
Выходной файл должен содержать одно число — минимальное значение x, для которого Алиса сможет добиться того, чтобы Боб не смог выбрать призы с суммарной ценностью больше x.

Пример
Ввод:
10 2
1 2 4 5 2 4 2 2 1 6
Вывод:
7

Пояснение к примеру
В приведенном примере Алиса может, например, выбрать 4-й и 5-й призы. После этого для Боба оптимально выбрать 9-й и 10-й призы с суммарной ценностью 7.

ID 21996. Кладовка из Простоквашино

Сразу же после заселения в новый дом в Простоквашино кот Матроскин, Шарик и дядя Фёдор затеяли ремонт. Непосредственно перед его началом они обнаружили, что в доме отсутствует кла- довка для стройматериалов, и наспех пристроили её к дому. Как только вспомогательное строение было готово, встал вопрос о необходимости провести туда электричество и повесить лампочку.

Обсудив вопросы электрификации новых помещений с почтальоном Печкиным, наши герои узна- ли много полезной информации. Чтобы посетители не мучились с выбором, в деревенском магазине продаётся только один вид лампочек, зато в неограниченных количествах. Стоит одна лампочка ни дорого, ни дёшево, а ровно C рублей. Правда, лампочки в магазине не самые качественные, и вклю- чить каждую из них можно только K раз, а на K + 1 включение она перегорает. Недостаток этот компенсируется тем, что во включенном состоянии лампочка перегореть не может. К сожалению, электроэнергия в Простоквашино недешевая, и каждая минута работы лампочки обойдется дяде Фёдору и его друзьям в D рублей.

Узнав всё это, экономный Матроскин составил поминутный график из N предполагаемых посе- щений кладовки. Каждый визит в новое помещение задаётся моментом входа ai и моментом выхода bi . Таким образом, i-й визит продолжается ровно b_i − a_i минут.

Разумеется, во время посещения свет в кладовке должен быть включён. Если в начале очередного визита лампочка не горит, то посетитель сразу её включает, а вот уходя он может как выключить свет, так и оставить его включенным. Если во время очередного включения лампочка перегорает, то её приходится немедленно заменить. Теперь Матроскина интересует минимальное количество рублей, которое придётся потратить, чтобы выполнить все запланированные визиты в кладовку. Изначально в помещении уже висит новая лампочка в выключенном состоянии.

Формат входных данных
В первой строке входных данных записаны четыре целых числа N, K, C, D — количество пла- нируемых посещений кладовки, количество успешных включений для одной лампочки, стоимость покупки лампочки и стоимость минуты работы лампочки соответственно (1 <= N, K <= 200 000, 1 <= C, D <= 10⁹ ). В следующих N строках даны по два целых положительных числа ai и bi , описывающих пред- полагаемые визиты в кладовку (1 <= a_i < b_i <= 10⁹ ). Посещения не пересекаются по времени и упорядочены, то есть b_i < a_i+1.

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

ID 27042. Падающее домино

ID 27041. Двумерный дождь

ID 24761. Путь в никуда

Колобку снится странный сон.
В нём Колобок находится на клетчатом поле размера n × m в клетке с координатами (x, y).
Изначально Колобок смотрит вдоль положительного направления оси X. Затем он начинает идти по полю со следующей закономерностью:
• Пройти на одну клетку вперед. Повернуть на 90^o вправо.
• Пройти на одну клетку вперед. Повернуть на 90^o вправо.
• Пройти на две клетки вперед. Повернуть на 90^o вправо.
• Пройти на две клетки вперед. Повернуть на 90^o вправо.
• Пройти на три клетки вперед. Повернуть на 90^o вправо.
• Пройти на три клетки вперед. Повернуть на 90^o вправо.
• Пройти на четыре клетки вперед. Повернуть на 90^o вправо.
• И так далее...

Движение продолжается до тех пор, пока Колобок не выйдет за границы поля. После этого Колобок просыпается.

Утром Колобок решил проанализировать свой сон. Он догадался, что в каждой клетке он был максимум один раз, но никак не может вспомнить, сколько клеток он посетил. Колобок просит вас написать программу, которая посчитает количество посещённых им клеток.




Формат входного файла
В первой строке входного файла находятся два натуральных числа n, m (1 ≤ n, m ≤ 10⁹ ) — размеры доски вдоль оси X и оси Y соответственно. Во второй строке находятся два натуральных числа x, y (1 ≤ x ≤ n; 1 ≤ y ≤ m) — координаты стартовой позиции колобка.

Формат выходного файла
В выходной файл выведите одно число — количество клеток, посещенных Колобком во сне.
 

ID 27215. Modern Art

ID 39474. Сумма подотрезка

Дан неизменяемый массив длины n и q запросов типа “вычислить сумму подотрезка массива с l по r”. Выведите ответ на каждый запрос.

Входные данные
В первой строке дано число n – размер массива (\(1 <= n <= 10^5\)). Во второй строке дано n чисел – элементы массива. Числа по модулю не превосходят \(10^9\). В третьей строке дано число q – кол-во запросов (\(1 <= q <= 10^5\)). Далее дано q строк, в каждой из которых дано 2 числа: l и r (\(1 <= l <= r <= n\)).

Выходные данные
Выведите ответы на все запросы, каждый в отдельной строке.
 

Примеры

ID 48795. Разность сумм

Дан массив целых чисел (nums) с индексацией, начинающейся с 0. Сформируйте новый массив целых чисел (ans), в котором i-й элемент вычисляется по формуле:

 ans[i] = |leftSum[i] - rightSum[i]|.

Где:

leftSum[i] - сумма элементов, стоящих слева от элемента nums[i]. Если таких элементов нет, то leftSum[i] = 0.
rightSum[i] - сумма элементов, стоящих справа от элемента nums[i]. Если таких элементов нет, то rightSum[i] = 0.

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

Формат входных данных
Первая строка содержит число n (n <= 10⁵). Во второй строке записаны n целых чисел numsi - элементы массива nums (|numsi| < 10⁶).

Формат выходных данных
Выведите на экран n чисел - элементы нового массива на экран в одну строку, разделяя элементы одним пробелом.

ID 49127. Средний индекс массива

Дан массив целых чисел nums (первый элемент массива имеет индекс 0). Найдите наименьший "средний" индекс массива.

Средний индекс - это индекс, для которого выполняется условие: сумма элементов слева от индекса равна сумме элементов справа от индекса (не включая сам элемент со средним индексом). То есть

leftSum[middle] = rightSum[middle].

Где:

middle - средний индекс массива.
leftSum[middle] - сумма элементов, стоящих слева от элемента nums[middle]. Если таких элементов нет, то leftSum[middle] = 0. 
rightSum[middle] - сумма элементов, стоящих справа от элемента nums[middle]. Если таких элементов нет, то rightSum[middle] = 0.

Формат входных данных
Первая строка содержит натуральное число N (1 <= N <= 105) - количество элементов в массиве nums. Вторая строка содержит N чисел numsi - элементы массива nums (|numsi|<=1000, 0 <= i < N).

Формат выходных данных
Выведите одно число - наименьший "средний" индекс массива. Если такого индекса нет, то выведите -1.

ID 49190. Подсчет прибыли

ID 49321. Опорная точка

Назовем опорным числом последовательности натуральных чисел - целое число x, такое что:

• Сумма всех элементов между 1 и x включительно равна сумме всех элементов между x и n включительно.

Например, для числовой последовательности из 8 элементов (числа от 1 до 8 включительно) опорным числом будет число 6 (1+2+3+4+5+6 = 6+7+8).

Для заданного натурального числа n, найдите минимальную опорную точку последовательности натуральных чисел от 1 до n.

Формат входных данных
Программа получает на вход натуральное число n (1 <= n <= 2000).

Формат выходных данных
Выведите минимальную опорную точку последовательности натуральных чисел от 1 до n. Если такой точки не существует, вернуть -1.

ID 49446. Битовый баланс двоичной строки

Битмен ищет битовый баланс у двоичной строки (строки, состоящей только из 0 и 1). Чтобы найти битвой баланс, Битмен разбивает строку на две непустые подстроки (левую подстроку и правую подстроку). Затем Битмен считает сумму количества нулей в левой подстроке и количества единиц в правой подстроке. Битовый баланс двоичной строки равен максимальной сумме, полученной после какого-либо разбиения строки на подстроки.

Формат входных данных
На вход подается строка (2 <= длина строки <= 1000). Строка состоит только из символов 0 и 1. 

Формат выходных данных
Выведите одно число - битовый баланс строки.


Примечание
В тестовом примере все возможные способы разить строку на 2 непустые строки следующие:

left = "0" и right = "11101", сумма = 1 + 4 = 5 
left = "01" и right = "1101", сумма = 1 + 3 = 4 
left = "011" и right = "101", сумма = 1 + 2 = 3 
left = "0111" и right = "01", сумма = 1 + 1 = 2 
left = "01110" и right = "1", сумма = 2 + 1 = 3

Битовый баланс равен максимальному значению суммы, следовательно ответ 5.

ID 50403. Вася и Петя

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

Однажды Петя в очередной раз написал грустную песню про любовь и поспешил показать ее Васе. Песня представляет собой строку из маленьких букв английского алфавита. У Васи сразу возникло \(q\) вопросов про эту песню. Каждый вопрос представляет собой некоторый отрезок песни с позиции \(l\) до позиции \(r\) включительно. Вася рассматривает подстроку, образованную символами на этом отрезке, а затем повторяет каждую букву в этой подстроке \(k\) раз, где \(k\) — порядковый номер соответствующей буквы в алфавите. Например, если Вася выбрал подстроку <<abbcb>>, то он повторит букву <<a>> один раз, каждую из букв <<b>> — по два раза, букву <<c>> — три раза, и полученная строка будет равна <<abbbbcccbb>>, ее длина равна 10. Вася интересуется именно длиной полученной строки.

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

Формат входных данных
В первой строке вводятся числа \(n, q\) (\(1\leq n\leq 100\,000, 1\leq q \leq 100\,000\)) — длина песни и количество вопросов.

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

В следующих \(q\) строках даны описания вопросов. Каждое описание состоит из двух чисел \(l\) и \(r\) \((1 \leq l \leq r \leq n)\) — границы каждого из вопросов.

Формат выходных данных
Выведите \(q\) строк — для каждого вопроса выведите длину строки, которую выпишет Вася.

В первом примере Васю интересуют три вопроса. В первом вопросе Вася рассматривает подстроку <<aba>>, которая превратится в <<abba>>, а значит, ответ на этот вопрос равен 4. Во втором вопросе Вася рассматривает подстроку <<baca>>, которая превратится в <<bbaccca>>, а значит, ответ на этот вопрос будет равен 7. В третьем вопросе Вася рассматривает всю строку <<abacaba>>, которая превратится в <<abbacccabba>> — строку длины 11.

Для получение номера буквы можно использовать следующий код:

• В языке python3 или pypy3 выражение ord(x) - 96, например ord(a) - 96 равно 1, а ord(x) - 96 равно 24.

• В языке c++ выражение x - 96, например a - 96 равно 1, а x - 96 равно 24.

• В языке pascal выражение ord(x) - 96, например ord(a) - 96 равно 1, а ord(x) - 96 равно 24.

ID 57757. Длина последовательности

Рассмотрим отрезок целых неотрицательных чисел от \(l\) до \(r\). Запишем их подряд в десятичной системе счисления, получив строку \(a\). Например, если \(l=3\), \(r=10\), то \(a=345678910\).

Найдите такой отрезок подряд идущих неотрицательных чисел \([l,r]\) (\(0 \le l \le r \le 10^{18}\)), что записанная для него строка \(a\) имеет длину ровно \(S\), а количество чисел на отрезке \([l,r]\) максимально.

Формат входных данных
Первая строка содержит одно целое число \(S\) (\(1 \le S \le 10^{18}\)).

Формат выходных данных
В первой строке выведите длину отрезка \([l,r]\). Если решения не существует, выведите одно целое число \(-1\).

Если решение существует, во второй строке выведите искомые границы отрезка \(l\) и \(r\).

Если существуют несколько решений, выведите любое из них.