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

В маленьком городе N, где нет ни интернета, ни телефонов, живут лучшие друзья Коля, Маша, Саша и Наташа. В очередной зимний день им очень хотелось провести время, играя в какую-нибудь игру, но такую, чтобы игра была не очень быстрой. Потому Маша предложила ребятам сыграть в своего рода модифицированную карточную версию игры «Пьяница» под названием «Круговерть_2».
Правила игры оказались следующими:

• ·игрокам заранее раздают поровну перетасованную колоду из52 карт (четыре масти: червы, бубны, трефы, пики, в каждой из которых 13 карт), таким образом у каждого игрока оказывается своя колода карт, стоящая в виде стопки, расположенной рубашкой вниз;
• ·каждый ход игроки выкладывают на стол по одной картесверху своей колоды на стол, по порядку слева-направо (первый игрок, второй игрок, третий и четвёртый), далее происходит определение победителей:
•     - если карты одной масти, то побеждает тот, у кого картабыла наибольшего значения (порядок карт в порядке их значения по возрастанию: туз, 2-10, валет, дама, король); туз - самая слабая карта;
•     - если карты разных мастей, то побеждает тот, у когомасть выше по значению (порядок мастей по возрастанию: червы, бубны, трефы, пики);
•     - если карт высшей масти несколько, то рассматриваетсяопределение наибольшего значения среди этих карт (например, выложили 10 червы, 8 бубны, 7 трефы, 8 трефы, то карты разных мастей, потому выбирается наибольшая масть – в данном случае трефы, таких карт две, среди них самая наибольшая 8 трефы, потому побеждает игрок 4);
• ·победитель забирает четыре карты в свою колоду по порядку,кладя сперва карту первого игрока под низ колоды, затем второго, третьего, четвёртого;
• ·побеждает тот игрок, который заберёт все картыпротивников.

Коля очень любит программирование, потому он решил заранее рассчитать, сколько им понадобится ходов, чтобы был определён победитель (у кого будут все 52 карты), потому ему требуется помочь написать программу, которая по входным данным игры определит через сколько ходов будет определён победитель игры. Если же за 1000 ходов победитель так и не определится, то вывести, сколько карт оказалось у первого игрока, у второго, третьего, четвёртого.
Входные данные:
на первых 13 строках подаются карты первого игрока (в порядке их нахождения в стопке карт),
далее на 13 строках подаются карты второго игрока (в порядке их нахождения в стопке карт),
далее на 13 строках подаются карты третьего игрока (в порядке их нахождения в стопке карт),
далее на 13 строках подаются карты четвёртого игрока (в порядке их нахождения в стопке карт).
Все карты подаются в формате <масть>, <значение>.
Масти обозначаются следующим образом (одна латинская буква в нижнем регистре):

• c – червы;
• b – бубны;
• t – трефы;
• p – пики.

Значения карт с картинками обозначаются следующим образом (одна латинская буква в нижнем регистре):

• t – туз;
• v – валет;
• d – дама;
• k – король.

Например:

• (t,10) – десятка треф;
• (c, t) – туз червей.

Выходные данные:
Если за 1000 ходов (включительно) кто-то победит, то вывести количество ходов и номер победившего игрока (например, 340 2, что означает, что за 340 ходов победил игрок №2).
Если за 1000 ходов (включительно) минимум у двух игроков останутся карты (никто не победит), то вывести количество карт по завершении 1000-го хода у первого игрока, у второго, у третьего, у четвёртого на одной строке через пробел (например, 48 3 1 0).
Примечание
•карты перечисляются в вводе так, как они лежат сверху-вниз,если сперва дали туз, затем 10, то на дне колоды лежит 10, а на верху туз, который будет вытащен первым.

В маленьком городе N, где нет ни интернета, ни телефонов, живут лучшие друзья Коля и Маша. В очередной зимний день им очень хотелось провести время, играя в какую-нибудь игру, но такую, чтобы игра была не очень быстрой. Потому Маша предложила Коле сыграть в своего рода модифицированную карточную версию игры «Пьяница» под названием «Круговерть».
Правила игры оказались следующими:
·игрокам заранее раздают поровну перетасованную колоду из52 карт (четыре масти: червы, бубны, трефы, пики, в каждой из которых 13 карт), таким образом у каждого игрока оказывается своя колода карт, стоящая в виде стопки, расположенной рубашкой вниз;

• каждый ход игроки выкладывают на стол по одной картесверху своей колоды на стол, далее происходит определение, кто заберёт карты:

               - если карты одной масти, то забирает карты тот, у когокарта была наибольшего значения (порядок карт в порядке их значения по возрастанию: туз, 2-10, валет, дама, король); туз - самая слабая карта; 
               - если карты разных мастей, то забирает карты тот, у когомасть выше по значению (порядок мастей по возрастанию: пики, червы, бубны, трефы);

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

Коля очень любит программирование, потому он решил заранее рассчитать, сколько им понадобится ходов, чтобы был определён победитель (у кого не будет карт), потому ему требуется помочь написать программу, которая по входным данным игры определит через сколько ходов будет определён победитель игры. Если же за 1000 ходов победитель так и не определится, то вывести, сколько карт оказалось у первого игрока и сколько у второго.
Входные данные:
на первых 26 строках подаются карты первого игрока (в порядке их нахождения в стопке карт),
далее на 26 строках подаются карты второго игрока (в порядке их нахождения в стопке карт).
Все карты подаются в формате <масть>, <значение>.
Масти обозначаются следующим образом (одна латинская буква в нижнем регистре):

• c – червы;
• b – бубны;
• t – трефы;
• p – пики.

Значения карт с картинками обозначаются следующим образом (одна латинская буква в нижнем регистре):

• t – туз;
• v – валет;
• d – дама;
• k – король.

Например:

• (t,10) – десятка треф;
• (c, t) – туз червей.

Выходные данные: 
Если за 1000 ходов (включительно) кто-то победит, то вывести количество ходов и номер победившего игрока (например, 340 2, что означает, что за 340 ходов победил игрок №2).
Если за 1000 ходов (включительно) у всех останутся карты (никто не победит), то вывести количество карт по завершении 1000-го хода у первого игрока и у второго на одной строке через пробел (например, 50 2).
Примечание
•карты перечисляются в вводе так, как они лежат сверху-вниз,если сперва дали туз, затем 10, то на дне колоды лежит 10, а на верху туз, который будет вытащен первым.

Рассмотрим последовательность целых чисел длины N. По ней с шагом 1 двигается “окно” длины K, то есть сначала в “окне” видно первые K чисел, на следующем шаге в “окне” уже будут находиться K чисел, начиная со второго, и так далее до конца последовательности. Требуется для каждого положения “окна” определить минимум в нём.

Входные данные
В первой строке входных данных содержатся два числа N и K (1 ≤  N ≤  150000, 1 ≤ K ≤ 10000, K ≤  N) – длины последовательности и “окна”, соответственно. На следующей строке находятся N чисел – сама последовательность.

Выходные данные
Выходые данные должны содержать N − K + 1 строк – минимумы для каждого положения “окна”.

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

Однажды Петя в очередной раз написал грустную песню про любовь и поспешил показать ее Васе. Песня представляет собой строку из маленьких букв английского алфавита. У Васи сразу возникло \(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.

 

Петя открыл цветочный магазин. Магазин Пети занимается изготовлением и продажей букетов. Всего существует \(n\) видов цветов, занумерованных от 1 до \(n\). Каждый букет, чтобы быть гармоничным и красивым, должен состоять из цветов всех видов, по одной штуке каждого вида. В магазине уже есть \(a_i\) штук цветов вида \(i\). На цветочной базе можно купить цветок любого вида за 1 рубль.

Определите, сколько букетов сможет собрать Петя, если потратит не более \(x\) рублей на покупку цветов на базе. Ответьте на \(q\) запросов с различными \(x_i\).

Формат входных данных
В первой строке входных данных находятся два целых числа \(n\) и \(q\) (\(1 \le n, q \le 10^5\)) — количество различных типов цветов и количество запросов.

Во второй строке находятся \(n\) целых чисел \(a_1, a_2, \cdots, a_n\) (\(0 \le a_i \le 10^9\)) — количество цветов каждого вида, имеющихся в магазине.

В третьей строке находятся \(q\) целых чисел \(x_1, x_2, \cdots, x_q\) (\(0 \le x_i \le 10^9\)) — запросы Пети.

Формат выходных данных
Выходной файл должен содержать \(q\) чисел, где \(i\)-е число это максимальное количество букетов, которое можно собрать потратив не более \(x_i\) рублей.

Примечание
В первом примере у Пети изначально есть 1 цветок первого типа и 0 цветов второго типа.

В первом запросе у него есть 1 рубль, он покупает цветок второго типа и делает 1 букет.

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

В третьем запросе у него есть 5 рублей, он покупает 2 цветка первого типа и 3 цветка второго типа и делает 3 букета.

Битмен ищет битовый баланс у двоичной строки (строки, состоящей только из 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.

Назовем опорным числом последовательности натуральных чисел - целое число 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.

Дан массив целых чисел 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.

Дан массив целых чисел (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 чисел - элементы нового массива на экран в одну строку, разделяя элементы одним пробелом.

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

 

 

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

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

Выходные данные
Выведите на экран два числа через пробел: максимальную сумму подпоследовательности, кратную K и количество таких подпоследовательностей.
 

Примеры

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

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


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

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

Примеры

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

 
 

Дан неизменяемый массив длины 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\)).

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

Примеры

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

Громозека раздавал N земным детям, стоящим по кругу, привезенные подарки. Чтобы не было никому обидно, Громозека решил, что будет каждый раз давать подарок K-му ребенку. Ребенок, получивший подарок с радостью выбегал из круга, а все остальные смыкали круг. 
Определите в каком порядке дети получали подарки.

Входные данные
Входная строка содержит числа N ( 1 <= N <= 10000 ) и K ( 1 <= K <= 10000 ), разделённые пробелом.

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

Примеры

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

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

Пояснение

Подстрока строки - это строка, полученная удалением нуля или более символов из начала и конца строки исходной строки. Например, для строки KOTS подстроками будут строки KO, KOT, OT, OTS, (пустая строка) и другие, но не OK.


Входные данные
В первой строке записаны два числа N (2<=N<=10⁵) и Q (1<=Q<=10⁵). Во второй строке записана строка S длины N. Каждый символ строки это S, T, O или K. Далее идут Q строк по 2 числа в каждой: li и ri (1 <= l_i< r_i <= N).

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

Примеры

№	Входные данные	Выходные данные
1	8 3 OKOKTOKS 3 7 2 3 1 8	2 0 3

У вас есть строка 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 строк.
 

Примеры

№	Входные данные	Выходные данные
1	5 3 abcdc 1 5 2 3 3 5	13 5 10