| Условие задачи | | Прогресс |
|
Темы:
Префиксные суммы(минимумы, ...)
Дан неизменяемый массив длины 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 |
| |
![]()
|
|
Темы:
Префиксные суммы(минимумы, ...)
Наталья Коршунова очень скучает по Григорию Мелехову и хочет вернуться к нему. Но, к сожалению, Григорий любит Аксинью, поэтому Наталья решила доказать любимому, что она лучше нее.
Для этого Наталья отправилась к Григорию и заявила, что она может решить любую задачу, какую бы он ни предложил. Мелехов принял вызов.
Григорий дает Наталье массив A, состоящий из n целых неотрицательных чисел. Затем он просит ее сделать q однотипных операций, заключающихся в следующем: "Даны числа l, r и k. Далее для каждого индекса i от l до r происходит подстановка числа k вместо числа Ai и считается побитовое исключающее “или” всех чисел на отрезке \([l;r]\), после чего на iое место опять возвращается число Ai".
Таким образом, происходит \(r – l + 1\) независимых подстановок, не меняющих массив, и соответственно \(r – l + 1\) результатов побитового исключающего “или”. Наталье необходимо сообщить Григорию побитовое исключающее “или” всех результатов подстановок (для лучшего понимания ознакомьтесь с примерами).
Помогите Наталье Коршуновой справиться с этой задачей! Тогда Григорий точно вернется к ней!
Входные данные
В первой строке дано целое число n (\(1 <= n <= 10^5\)) – количество элементов массива.
Во второй строке содержится n целых неотрицательных чисел, не превышающих по значению \(10^8\).
В третьей строке дано целое число q (\(1 <= q <= 10^5\)) – количество запросов.
Далее содержится q строк, в каждой из которых содержится 3 целых числа: l, r, k (\(1 <= l <= r <= n\), \(0 <= k <= 10^8\)).
Выходные данные
Вам необходимо вывести q ответов на каждый запрос в одной строке через пробел.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
1 2 3 4 5
2
1 3 7
4 5 10
|
7 1 |
Пояснение
Первый запрос:
1) 7 ⊕ 2 ⊕ 3 = 6
2) 1 ⊕ 7 ⊕ 3 = 5
3) 1 ⊕ 2 ⊕ 7 = 4
6 ⊕ 5 ⊕ 4 = 7
Ответ: 7.
Второй запрос:
1) 10 ⊕ 5 = 15
2) 4 ⊕ 10 = 14
15 ⊕ 14 = 1
Ответ: 1.
| |
![]()
|
|
Темы:
"Два указателя"
Префиксные суммы(минимумы, ...)
Аксинья любит Григория, но она замужем за Степаном. Со своим мужем она несчастна, поэтому время, которое она проводит с ним можно характеризовать отрицательным показателем счастья Аксиньи (\(a_i < 0\)), а то время, которое она проводит с Григорием, - положительным показателем счастья (\(a_i > 0\)). Известно, что Аксинья проводит один день либо с мужем, либо с любовником.
Найдите максимальное суммарное счастье за L дней, в которые Аксинья будет проводить с мужем не более C дней.
Входные данные
В первой строке подается 3 числа: N – кол-во дней, L и C (\(1 <= L, C <= N <= 1 000 000\)).
Во второй строке содержится N чисел a_i (\(1 <= |a_i| <= 1 000 000 000\)).
Входные данные
Требуется вывести ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5 3 3
1 -1 2 -2 3 |
3 |
| |
![]()
|
Темы:
Префиксные суммы(минимумы, ...)
Чубатый учит Григория Мелехова выполнять баклановский удар шашкой. В качестве целей, они используют n деревьев, стоящих в ряд и пронумерованных от 1 до n. Чубатый, оценил прочность всех деревьев натуральными числами, и записал их. За каждое дерево, которое Мелехов смог разрубить, он получает количество очков равное числу, записанному на дереве, а если не смог - то теряет столько же.
Чубатый просит Григория выполнить удары на деревьях с l по r, в порядке возрастания их номеров. Мелехов недавно ушиб плечо, потому он может успешно срубить дерево через раз, т. е. если он срубил дерево с номером i, то он не сможет срубить дерево с номером i + 1, но сможет срубить дерево с номером i + 2 и т. д.
Чубатый m раз попросил Григория выполнить удары, но он забыл, какие деревья Мелехов смог срубить. Помогите ему определить, сколько очков набрал Григорий за каждую попытку.
Входные данные
В первое строке содержатся 2 числа n и m (\(1 <= n, m <= 100000\))
Во второй строке содержатся n чисел - прочность всех деревьев, где на позиции i написана прочность дерева i.
В следующих m строках содержатся пары чисел l и r (\(1 <= l <= r <= n\)), означающие какой отрезок деревьев попросил срубить Чубатый.
Выходные данные
На каждый запрос выведите сколько очков в эту попытку заработал Григорий.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6 6
1 2 3 4 5 6
1 6
1 5
2 6
2 5
2 4
2 2
|
-3
3
4
-2
3
2
|
| |
![]()
|
|
Темы:
Префиксные суммы(минимумы, ...)
Малая теорема Ферма
Остатки
Быстрое возведение в степень
Банда Фомина состоит из n групп, в каждой из которых ai человек. Планируется провести q рейдов. В i-ом рейде будет участвовать ровно один разбойник из каждой группы, номер которой лежит в отрезке \([l_i, r_i]\).
Мелехов тоскует, поэтому для каждого рейда он решил посчитать количество возможных отрядов по модулю \(10^9 + 7\). Однако Григорий постоянно находится в раздумьях о смысле жизни и поиске правды, поэтому он не может сконцентрироваться на расчетах и просит вас помочь.
Входные данные
В первой строке дано число n (\(1 <= n <= 10^5\)) – количество групп в банде Фомина.
Во второй строке дано n натуральных чисел ai (\(1 <= a_i <= 10^6\)) – количество человек в i-ой группе.
В третьей строке дано число q – количество рейдов.
Далее дано q строк, в каждой из которых дано два числа – li и ri (\(1 <= l_i <= r_i <= n\)) – номера групп, участвующих в i-ом рейде.
Выходные данные
Выведите q чисел, каждое в отдельной строке – ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6
1 3 7 1 4 100
3
1 3
3 4
2 6 |
21
7
8400 |
| |
![]()
|
Темы:
Префиксные суммы(минимумы, ...)
Банда Фомина состоит из n групп, в каждой из которых ai человек. Планируется провести q рейдов. В i-ом рейде будет участвовать ровно один разбойник из каждой группы, номер которой лежит в отрезке \([l_i, r_i]\).
Мелехов тоскует, поэтому для каждого рейда он решил посчитать количество возможных отрядов по модулю \(10^9 + 7\). Однако Григорий постоянно находится в раздумьях о смысле жизни и поиске правды, поэтому он не может сконцентрироваться на расчетах и просит вас помочь.
Входные данные
В первой строке дано число n (\(1 <= n <= 10^5\)) – количество групп в банде Фомина.
Во второй строке дано n натуральных чисел ai (\(1 <= a_i <= 2\)) – количество человек в i-ой группе.
В третьей строке дано число q – количество рейдов.
Далее дано q строк, в каждой из которых дано два числа – li и ri (\(1 <= l_i <= r_i <= n\)) – номера групп, участвующих в i-ом рейде.
Выходные данные
Выведите q чисел, каждое в отдельной строке – ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6
1 2 1 1 2 2
3
1 3
3 4
2 6
|
2
1
8 |
| |
![]()
|
Темы:
Куча
Префиксные суммы(минимумы, ...)
Кот Гусь подготовил для Ника Фьюри прямоугольную таблицу a размера \(n \cdot m\), содержащую числа от 0 до p−1. Ник Фьюри сразу понял, что каждое число в этой таблице выбрано случайно равновероятно от 0 до p−1, независимо от остальных.
Ваша задача — найти прямоугольную подматрицу этой таблицы, в которой сумма делится на p. Среди всех таких подматриц нужно найти ту, в которой сумма элементов максимальна.
Формально, вам необходимо найти такие \(1 <= i_1 <= i_2 <= n\), \(1 <= j_1 <= j_2 <= m\), что сумма ax,y по всем \(i_1 <= x <= i_2\), \(j_1 <= y <= j_2\) делится на p, и среди таких имеет максимальную сумму.
Входные данные
В первой строке расположено три целых числа n, m, p (\(1 <= n·m, p <= 1 000 000\)) — размерности матрицы и число, на которое должна делится сумма подматрицы.
В следующих n строках расположено по m целых чисел, j-е число в i-й строке равно ai,j (\(0 <= a_{i,j} <= p ? 1\)).
Гарантируется, что каждое число в a выбрано независимо случайно равновероятно от 0 до p−1.
Выходные данные
Выведите одно целое число — максимальную сумму прямоугольной подматрицы, в которой сумма делится на p. Если таких нет, выведите 0.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6 7 5
0 0 3 0 1 0 4
0 2 3 0 2 2 1
2 4 1 4 4 0 3
1 1 0 2 0 3 2
3 0 3 1 0 1 2
1 2 0 0 3 3 1
|
65 |
| |
![]()
|
|
Темы:
Префиксные суммы(минимумы, ...)
Пастбище Фермера Джона может рассматриваться как NхN решётка (\(1<=N<=500\)) квадратных ячеек с травой (как большая шахматная доска). Из-за изменчивости почвы, трава в некоторых ячейках зеленее, чем в других. Каждая ячейка (i,j) описывается целым числом - уровнем зелёности G(i,j), в интервале \(1…200\).
Фермер Джон хочет сделать фотографию прямоугольной подрешётки своего пастбища. Он хочет, чтобы минимальная из величин G на его фотографии была ровна 100. Помогите ему посчитать, сколько таких различных фотографий он сможет сделать. Подрешётка может быть размером от всего пастбища и до одной ячейки. Всего существует \(N^2(N+1)^2/4\) различных подрешёток, для хранения такого числа используйте 64-битное целое (типа long long в C++).
Входные данные
Первая строка содержит N. Каждая из следующих N строк содержит N целых чисел и все вместе они описывают величины G(i,j) для пастбища NхN .
Выходные данные
Выведите количество различных фотографий, которые может сделать Фермер Джон, т.е. количество прямоугольных подрешёток, в которых минимальный уровень "зелёности" ровно 100.
Заметим, что для ответа требуется использовать 64-битную целую переменную типа long long в C++.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
57 120 87
200 100 150
2 141 135 |
8 |
| |
![]()
|
|
Темы:
Бинарный поиск в массиве
Префиксные суммы(минимумы, ...)
Володя хочет красиво поздравить свою жену с годовщиной их свадьбы и собирается подарить ей букет из n цветов.
Придя в цветочный магазин, Володя обнаружил, что букет можно составлять из цветов m различных видов, причём количество цветов каждого вида не ограничено. Володя знает, что от первого цветка i-го вида в букете его супруга становится счастливее на ai, а от каждого следующего цветка
такого вида она становится счастливее на bi. То есть, если в букете xi > 0 цветов вида i, то от цветов этого вида жена Володи становится счастливее на ai + (xi − 1) · bi.
Как любой любящий муж, Володя хочет как можно сильнее порадовать свою супругу. Поэтому ему хочется знать, на какую максимальную величину может увеличиться её счастье от букета, набранного из доступных в магазине цветов.
Формат входных данных
В первой строке вводятся два целых числа n и m (1 ≤ n ≤ 109 , 1 ≤ m ≤ 100 000) — требуемое
количество цветов в букете и количество доступных видов цветов.
Каждая из следующих m строк описывает i-й вид цветов и содержит два целых числа ai и bi (0 ≤ ai , bi ≤ 109 ) — увеличение счастья от первого цветка i-го вида и увеличение счастья от каждого последующего цветка этого вида.
Формат выходных данных
В единственной строке выведите одно число — максимальное увеличение счастья, которое может получить жена Володи от букета из n цветов.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4 3
5 0
1 4
2 2 |
14 |
| 2 |
5 3
5 2
4 2
3 1 |
16 |
| |
![]()
|
|
Темы:
Массивы
Префиксные суммы(минимумы, ...)
Динамическое программирование: один параметр
У нас есть сетка с 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.
Выходные данные
Для каждого теста выведите сумму маджиков, израсходованных во время этого теста. Вывод должен быть в порядке проведения тестов.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснения |
| 1 |
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8 |
5 |
- 4 записано Square (1,2).
- 6 записано в Square (3,3).
- 8 записано in Square (3,1).
Таким образом, сумма магических очков, израсходованных во время одного теста, составляет:
\((|3-1|+|3-2|)+(|3-3|+|1-3|)=5\).
|
| 2 |
4 2 3
3 7
1 4
5 2
6 8
2
2 2
2 2 |
0
0 |
Обратите внимание, что может быть тест, в котором фигура вообще не перемещается, и может быть несколько идентичных тестов. |
| 3 |
5 5 4
13 25 7 15 17
16 22 20 2 9
14 11 12 1 19
10 6 23 8 18
3 21 5 24 4
3
13 13
2 10
13 13 |
0
5
0 |
|
| |
![]()
|
|
Темы:
Динамическое программирование: один параметр
Префиксные суммы(минимумы, ...)
У вас есть строка s. Вы хотите сделать новую строку, записывая в ней каждую букву количество раз равное порядковому номеру этой буквы в алфавите. Например, s = "abcdc", новая строка s_new = "abbcccddddccc". Нам стало интересно, какая получится у вас длина строки, если выписать все символы исходной строки, начиная с символа l и заканчивая символом r. Всего у нас k запросов к вам.
Входные данные
В первой строке программа получает на вход два числа n и k (1<=n<=106, 1<=k<=106), где 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 |
| |
![]()
|
|
Темы:
Строки
Префиксные суммы(минимумы, ...)
Дана строка S длины N, состоящая из символов S, T, O и K. Дайте ответ на Q запросов следующего вида.
Запрос i(1 <= i <= Q): для заданных целых чисел li и ri (1 <= li< ri <= N), рассматривается подстрока S, начинающаяся с индекса li и заканчивающася индексом ri (оба включительно). Необходимо определить, сколько раз в этой строке втречается OK как подстрока?
Пояснение
Подстрока строки - это строка, полученная удалением нуля или более символов из начала и конца строки исходной строки. Например, для строки KOTS подстроками будут строки KO, KOT, OT, OTS, (пустая строка) и другие, но не OK.
Входные данные
В первой строке записаны два числа N (2<=N<=105) и Q (1<=Q<=105). Во второй строке записана строка S длины N. Каждый символ строки это S, T, O или K. Далее идут Q строк по 2 числа в каждой: li и ri (1 <= li< ri <= N).
Выходные данные
Выведите Q строк. I-я строка должна содержать ответ на i-й запрос.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
8 3
OKOKTOKS
3 7
2 3
1 8 |
2
0
3 |
| |
![]()
|
|
Темы:
Бинарный поиск
Префиксные суммы(минимумы, ...)
Цикл лекций в университете Флатландии посвящен изучению последовательностей.
Профессор называет последовательность целых чисел \(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 )\) .
Выходные данные
Выходной файл должна содержать одно целое число: минимальное возможное расстояние от последовательности во входном файле до гармоничной последовательности.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4
1 2 0 0 |
2 |
| |
![]()
|
|
Темы:
"Два указателя"
Префиксные суммы(минимумы, ...)
Дана последовательность из 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 последовательных 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 |
| |
![]()
|
|
Темы:
Хеш
Префиксные суммы(минимумы, ...)
Дана строка S = s1s2...sn и множество запросов вида (l1, r1, l2, r2). Для каждого запроса требуется ответить, равны ли подстроки sl1...sr1 и sl2...sr2.
Входные данные:
В первой строке дана строка S (1 <= |S| <= 105), состоящая из строчных латинских букв.
Во второй строке дано натуральное число q (1 <= q <= 105) - количество запросов.
В следующих q строках дано по 4 натуральных числа - l1, r1, l2, r2 (1 <= l1 <= r1 <= |S|, 1 <=l2 <= r2 <= |S|).
Выходные данные:
Для каждого запроса выведите '+', если подстроки равны, и '-', в противном случае.
Примеры:
| Входные данные |
Выходные данные |
abacaba
4
1 1 7 7
1 3 5 7
3 4 4 5
1 7 1 7 |
++-+ |
| |
![]()
|
|
Темы:
Хеш
Жадный алгоритм
Префиксные суммы(минимумы, ...)
Во время покраски забора Том Сойер написал на нем слово s. Однако затем он решил, что слова-палиндромы смотрятся красивее.
Теперь он хочет дописать к имеющемуся слову s справа другое слово g так, чтобы получившееся слово sg было палиндромом. Однако в целях экономии краски длина g должна быть как можно меньше.
Помогите Тому Сойеру определить слово g.
Входные данные:
В первой строке дано слово s (1 <= |s| <= 200000), состоящее из строчных латинских букв.
Выходные данные:
Выведите минимально возможное по длине слово g, которое нужно дописать, чтобы слово sg на заборе стало палиндромом. Если дописывать ничего не надо, то выведите '-'.
Примеры:
| Входные данные |
Выходные данные |
| abc |
ba |
| a |
- |
| |
![]()
|
|
Темы:
Хеш
Префиксные суммы(минимумы, ...)
Бинарный поиск
Бинарный поиск по ответу
Том Сойер и Гекльберри Финн вместе читают вслух вырезку из газеты. Но получилось так, что Том Сойер начал читать с i-ого символа, а Гекльберри Финн с j-ого.
Сколько букв они смогут прочитать, прежде чем обнаружат, что начали читать с разных мест или пока оба не дочитают до конца?
Входные данные:
В первой строке дана строка S (1 <= |S| <= 105), состоящая из строчных латинских букв - надпись из газетной вырезки.
В следующей строке дано натуральное число q - количество запросов.
В следующих q строках дано по два натуральных числа i и j - позиции, с которых начинают читать Том Сойер и Гекльберри Финн соответственно.
Выходные данные:
Выведите q строк, в каждой из которых должно быть одно целое число - количество символов, совпадающих при чтении подстрок, начинающихся с i-ого и j-ого символа.
Примеры:
| Входные данные |
Выходные данные |
abacaba
4
1 5
3 5
4 2
2 6 |
3
1
0
2 |
| |
![]()
|
|
Темы:
Хеш
Префиксные суммы(минимумы, ...)
Перебор
У Гекльберри Финна есть две строки 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 |
| |
![]()
|
|
Темы:
Хеш
Префиксные суммы(минимумы, ...)
Перебор
В начале XVIII века группа европейских исследователей прибыла на остров, населённый группой племён, никогда не вступавших в контакт с представителями европейской цивилизации.
Для успешного налаживания контактов с аборигенами руководитель группы планирует делать подарок вождю каждого встреченного племени. С этой целью он привёз длинную цепочку из стекляшек, похожих на драгоценные камни.
Представим цепочку как строку s, состоящую из маленьких букв английского алфавита, где каждая буква означает тип кусочка стекла на соответствующей позиции.
Исследователи собираются разрезать цепочку на некоторые фрагменты, после чего вручать ровно один фрагмент вождю каждого встреченного группой племени. Руководитель исследователей решил разделить цепочку на фрагменты согласно следующим правилами:
- Чтобы не тратить на разрезания много времени, каждый фрагмент должен являться группой соседних стекляшек цепочки, то есть подстрокой строки s.
- Все стекляшки должны быть использованы, то есть каждая стекляшка должна оказаться включённой ровно в один фрагмент.
- Поскольку исследователи не знают, как аборигены оценят те или иные виды стекляшек, они хотят, чтобы каждому вождю достался один и тот же набор стекляшек без учёта порядка. Иными словами, для любого типа стекляшек количество стекляшек этого типа должно быть одинаковым в каждом из фрагментов.
- Исследователи не знают, сколько племён обитает на острове, поэтому количество подготовленных фрагментов должно быть максимальным.
Помогите руководителю определить максимальное количество фрагментов, которое может получиться.
Входные данные:
В первой строке дана строка s (1 <= |s| <= 5000000).
Выходные данные:
Выведите одно число - максимально возможное количество фрагментов, на которое исследователи могут разрезать имеющуюся у них цепочку, не нарушая ни одного из условий, сформулированных руководителем группы.
Примеры:
| Входные данные |
Выходные данные |
| abbabbbab |
3 |
| aabb |
1 |
Пояснения:
В первом примере исследователи могут разбить цепочку 'abbabbbab' на фрагменты 'abb', 'abb', 'bab', тогда вождю каждого встреченного ими племени достанется по одной стекляшке типа 'a' и по две стекляшки типа 'b'.
Во втором примере строку невозможно поделить цепочку больше чем на один фрагмент, соблюдая все условия.
| |
![]()
|
|
Темы:
Динамическое программирование
Префиксные суммы(минимумы, ...)
У Макс в блокноте были записаны две строки 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 и t1 = si, t2 = si + 1, ..., tm = si + m - 1.
Красота строки s оценивается как максимальное количество непересекающихся вхождений строки t в нее. Макс может заменить некоторые из символов «?» на «a» или «b» (символы на разных позициях можно заменять на разные буквы). Макс хочет произвести замены так, чтобы красота строки s была максимально возможной. Из всех таких вариантов она хочет заменить как можно меньше символов «?». Найдите, сколько замен она должна сделать.
Входные данные:
Первая строка содержит одно целое число n (1 ≤ n ≤ 105) — длину строки s.
Вторая строка входных данных содержит строку s длины n, состоящую только из букв «a» и «b» латинского алфавита, а также символов «?».
Третья строка содержит целое число m (1 ≤ m ≤ 105) — длину строки t. Сама строка t содержит «a» на нечетных позициях, и «b» на четных.
Выходные данные:
Выведите единственное целое число — минимальное количество замен, которое должен сделать Вася, чтобы сделать красоту строки s максимально возможной.
Примеры:
| Входные данные |
Выходные данные |
5
bb?a?
1 |
2 |
9
ab??ab???
3 |
2 |
Пояснения:
В первом примере строка t имеет вид «a». Единственный оптимальный вариант — заменить все символы «?» на «a».
Во втором примере используя две замены можно получить строку «aba?aba??». Больше двух вхождений получить нельзя.
| |
![]()
|
|
Темы:
Алгоритм Мо
Префиксные суммы(минимумы, ...)
У Эвана есть любимое число k и массив ai длины n. Теперь он просит вас ответить на m запросов.
Для каждого запроса, задаваемого парой чисел l и r, требуется найти количество пар целых чисел i и j таких, что l ≤ i ≤ j ≤ r и xor чисел ai, ai + 1, ..., aj равен k.
Входные данные:
В первой строке даны целые числа n, m и k (1 ≤ n, m ≤ 105, 0 ≤ k ≤ 106) — длина массива, количество запросов и любимое число Эвана соответственно.
Во второй строке записаны n целых чисел ai (0 ≤ ai ≤ 106) — имеющийся у Эвана массив.
Дальше идут m строк. В i-й строке записаны числа li и ri (1 ≤ li ≤ ri ≤ 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 |
| |
![]()
|
|
Темы:
Префиксные суммы(минимумы, ...)
Вы решили съездить проведать своего друга из Озерска. Однако на въезде в город вас остановили и попросили решить задачу, чтобы удостовериться, что вы действительно можете проехать на территорию закрытого города.
Бинарная строка это строка, состоящая только из символов 0 и 1. Полицейский дал вам бинарную строку s1s2 ... sn. Нужно отсортировать эту строку (то есть превратить ее в строку вида 00 ... 0011 ... 11) за наименьшее количество операций. За одну операцию вы можете сделать следующее:
• Выбрать произвольный индекс в строке 1 <= i <= n;
• Для всех j >= i поменять значение в j-й позиции на противоположное, то есть если sj = 1, то сделать sj = 0, и наоборот.
Входные данные
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число t (1 <= t <= 104) количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит единственное целое число n (1 <= n <= 105) длину строки.
Вторая строка каждого набора входных данных содержит бинарную строку s длины n.
Гарантируется, что сумма n по всем наборам входных данных не превосходит 2 ·105.
Выходные данные
Для каждого набора входных данных выведите единственное целое число минимальное количество операций, которое потребуется сделать, чтобы отсортировать строку.
Примеры
| № |
Входные данные |
Выходные данные |
| 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.
| |
![]()
|
|
Темы:
Префиксные суммы(минимумы, ...)
Петя и Ваня решили придумать свои правила для игры Дартс. Они взяли круглое игровое поле и поделили его на сектора. Сектора нумеруются натуральными числами. Каждому сектору назначили количество очков, которое можно получить, если попасть дротиком в него. Перед началом игры выбирается нулевой сектор, который служит точкой отсчета: количество очков, которое набирает игрок, попадая в сектор, считается как количество очков, указанное в секторе, умноженное на расстояние (количество секторов) от нулевого сектора. При попадании в нулевой сектор количество очков равно нулю.
Поскольку заранее неизвестно, в какие именно сектора попадут игроки, нулевой сектор следует выбирать так, чтобы при однократном попадании во все сектора игрового поля игрок набирал максимальное количество очков.
Определите, какой сектор необходимо выбрать нулевым.
Входные данные
Первая строка входных данных содержит число 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) |
| |
![]()
|
|
Темы:
Префиксные суммы(минимумы, ...)
На каждом километре кольцевой автодороги с двусторонним движением установлены контейнеры для мусора. Длина кольцевой автодороги равна N километров. Нулевой километр и N-й километр автодороги находятся в одной точке. Известно количество мусора, которое накапливается ежедневно в каждом из контейнеров.
На автодороге работают два мусоровоза. Один едет по часовой стрелке, другой против. Оба мусоровоза выезжают из центра переработки одновременно навстречу друг другу и встречаются возле одного из контейнеров. Из одного контейнера вывезти мусор может только один мусоровоз. Время доставки мусора вычисляется как произведение количества мусора на расстояние от пункта до центра переработки. Центр переработки отходов открыли в одном из пунктов сбора мусора таким образом, чтобы общее время сбора мусора двумя мусоровозами было минимально.
Определите, возле контейнера с каким номером необходимо поставить центр переработки, чтобы потребовалось минимальное время мусоровозам для сбора мусора.
Входные данные
Первая строка входных данных содержит число N (1 <= N <= 10 000 000) – количество пунктов сбора мусора на кольцевой автодороге. В каждой из следующих N строк находится число – количество мусора в контейнере (все числа натуральные, количество мусора в каждом пункте не превышает 1000). Числа указаны в порядке расположения контейнеров на автомагистрали, начиная с первого километра.
Выходные данные
Выведите на экран одно число - ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
7
8
20
5
13
7
19
21 |
7 |
При таких исходных данных необходимо открыть центр переработки возле контейнера с номером 7:
Первый мусоровоз собирает мусор: 0 * 21 + 1 * 19 + 2 * 7 + 3 * 13 = 72
Второй мусоровоз потратит времени: 0 * 21 + 8 * 1 + 20 * 2 + 3 * 5 = 63
Итоговое время, которое потратят два мусоровоза: 72 |
| |
![]()
|
|
Темы:
Префиксные суммы(минимумы, ...)
Дана последовательность из N натуральных чисел. Известно, что сумма всех чисел последовательности не превышает 109. Рассматриваются все её непрерывные подпоследовательности, в которых количество нечётных чисел кратно K = 7. Найдите наибольшую сумму такой подпоследовательности.
Входные данные
Первая строка входных данных содержит одно число N (1 <= N <= 1 000 000) - количество чисел. Каждая из следующих N строк содержит одно натуральное число, не превышающее 1 000.
Входные данные
Выведите ответ на задачу
Пример организации исходных данных во входном файле (для К=4):
6
8
17
3
13
11
21
В этом наборе можно выбрать последовательности 8+17+3+13+11 (сумма 52) и 3+13+11+21 (сумма 48).
Ответ (для K = 4): 52.
| |
![]()
|