Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

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

Примеры:

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

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

Динамическое программирование Префиксные суммы(минимумы, ...)

✓ 22✗ 2111 100средняяВойти и решать

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

У Гекльберри Финна есть две строки 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

Перебор Префиксные суммы(минимумы, ...)Хеш

✓ 1✗ 01 000средняяВойти и решать

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

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

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

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

Примеры:

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

Жадный алгоритм Префиксные суммы(минимумы, ...)Хеш

✓ 3✗ 741 100средняяВойти и решать

Подстроки в строке#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|).

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

Примеры:

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

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

✓ 14✗ 126800средняяВойти и решать

Подпоследовательность с K числами#39528

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

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

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

Примеры

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

Алгоритмы обработки Префиксные суммы(минимумы, ...)

✓ 21✗ 1381 000средняяВойти и решать

Модифицированное демо - 2022#39481

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

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

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

Примеры

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

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

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

✓ 31✗ 1851 000средняяВойти и решать

Переключение между окнами#38849

Когда пользователь работает в операционной системе Windows, у него часто запущено несколько приложений. Каждое из приложений работает в отдельном окне. Для переключения между окнами используется комбинация клавиш «Alt+Tab». Эта комбинация делает активным окно, в котором пользователь работал перед тем, как перейти в текущее активное окно.

Чтобы переключиться в другое окно, можно нажать клавишу «Alt» и затем, не отпуская ее, несколько раз нажать клавишу «Tab». Чтобы понять, какое окно станет активным после этого, воспользуемся следующей моделью. Пусть запущено n приложений. Приложения в операционной системе организованы в виде списка и упорядочены по убыванию времени последней активности. То есть приложение, окно которого является активным в настоящий момент – первое в списке, приложение, окно которого было активно перед этим – второе, и т. д.

Если нажать клавишу «Alt» и затем, не отпуская ее, нажать клавишу «Tab» k раз, то активным станет окно приложения, которое находится на (k mod n) + 1-м месте в списке. Здесь a mod b означает остаток от деления a на b. Иными словами, операционная система рассматривает список как циклический, переходя после последнего элемента списка к первому.

При запуске нового приложения оно добавляется в начало списка.

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

Входные данные
В первой строке вводится целое число n – количество действий пользователя ( 1 ≤ n ≤ 1000). Следующие n строк содержат описание действий пользователя.

Запуск приложения описывается строкой «Run <имя приложения»>. Здесь «<имя приложения»> – строка из не более чем 100 латинских букв, цифр и пробелов. Она отделена от слова «Run» ровно одним пробелом. Все имена приложений различны. Большие и маленькие буквы считаются различными.

Переключение между приложениями описывается строкой «Alt+Tab+...+Tab», здесь подстрока «+Tab» повторена в точности столько раз, сколько раз пользователь нажал клавишу «Tab», не отпуская клавишу «Alt». Это количество не превышает 100.

Первая команда во входных данных – всегда команда «Run».

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

Примеры

№	Входные данные	Выходные данные
1	6 Run Mozilla Firefox Run Free Pascal Alt+Tab Run Miranda IM Alt+Tab+Tab Alt+Tab+Tab+Tab	Mozilla Firefox Free Pascal Mozilla Firefox Miranda IM Free Pascal Free Pascal

Задачи на моделирование Список

✓ 68✗ 178900средняяВойти и решать

Джерримендеринг#38777

Джерримендеринг — разделение территории на избирательные округа неестественным образом с целью искусственного изменения соотношения политических сил в них и, как следствие, в целом на территории проведения выборов. Например, при необходимости обеспечить победу на территории партии X (если от одного избирательного округа избирается один кандидат или один выборщик), нужно всех противников X сосредоточить по округам, где X не сможет выиграть, а всех сторонников X распределить так, чтобы они обеспечивали уверенную победу с небольшим перевесом в нужных округах. Например, в тесте из условия всего за X голосует 10 человек, а против X голосует 15 человек, но, благодаря специальному разделению по округам, X выигрывает в двух избирательных округах из трёх.
В этой задаче избирательная территория представляет собой улицу, на которой в ряд расположены N домов. В i-м доме проживает ai человек, и все они голосуют одинаково: либо за партию X, либо за другую партию. Улицу необходимо разбить на три избирательных округа, от каждого избирательного округа будет избираться один кандидат, и необходимо произвести такую нарезку улицы на три избирательных округа, чтобы минимум в двух округах из трёх выиграл кандидат от партии X. Кандидат от партии X выигрывает, если за него голосует более половины избирателей, проживающих в домах данного избирательного округа. Но чтобы вас не заподозрили в джерримендеринге, необходимо, чтобы каждый избирательный округ представлял собой непрерывный отрезок из номеров домов, то есть сначала вдоль по улице идут дома первого избирательного округа, затем — второго, затем — третьего. Каждый избирательный округ должен содержать как минимум один дом.

Входные данные
Первая строка входных данных содержит целое число N (3 <= N <= 10⁵ ) — количество домов на улице. Следующие N строк содержат по одному целому числу ai (0 < |ai | <= 10⁴ ). Если ai > 0, то в i-м доме проживает ai избирателей, голосующих за кандидата от партии X. Если ai < 0, то в i-м доме проживает |ai | избирателей, голосующих против кандидата от партии X.

Выходные данные
Если возможно разделить N домов на три округа так, что минимум в двух округах выигрывает кандидат от партии X, программа должна вывести в одной строке три целых положительных числа N1, N2, N3, N1 + N2 + N3 = N, соответствующих количеству домов в первом, втором и третьем избирательном округе от начала улицы. При таком разбиении минимум в двух округах из трёх должен выигрывать кандидат от партии X. Если возможно несколько таких разбиений, необходимо вывести любое из них.
Если искомое разбиение не существует, программа должна вывести одно число 0

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 -3 -5 3 -4 2 5 -3	4 1 2	На улице расположены 7 домов, избиратели в них распределены так: (−3, −5, 3, −4, 2, 5, −3). Правильный ответ: 4, 1, 2. При таком разбиении в первом округе оказываются 4 дома: (−3, −5, 3, −4). В этом округе за X голосует 3 избирателя, против — 12 избирателей и X разгромно проигрывает. В следующем округе один дом, в котором 2 избирателя голосуют за X, в этом округе X выиграет. В третьем округе два дома: (5, −3), и в этом округе X тоже выиграет. Итого X выигрывает в двух округах.

Префиксные суммы(минимумы, ...)реализация

✓ 14✗ 891 100средняяВойти и решать

Контейнеры#38599

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

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

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

Входные данные

В первой строке входных данных записано одно натуральное число N, не превосходящее 500. В следующих N строках описаны стопки контейнеров: сначала записано число k_i – количество контейнеров в стопке, а затем k_i чисел – виды товара в контейнерах в данной стопке, снизу вверх. В каждой стопке вначале не более 500 контейнеров (в процессе переноса контейнеров это ограничение может быть нарушено).

Выходные данные

Программа должна вывести описание действий автопогрузчика: для каждого действия напечатать два числа – из какой стопки брать контейнер и в какую стопку класть. (Обратите внимание, что минимизировать количество операций автопогрузчика не требуется.) Если задача не имеет решения, необходимо вывести одно число 0. Если контейнеры изначально правильно размещены по стопкам, то выводить ничего не нужно.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 4 1 2 3 2 0 0	1 2 1 3 1 2	Изначально в первой стопке лежат четыре контейнера – снизу контейнер с товаром первого вида, над ним – с товаром второго вида, над ним третьего, и сверху еще один контейнер с товаром второго вида. Вторая и третья стопки – пусты.

Стек

✓ 62✗ 2201 000средняяВойти и решать

Практический тест#38589

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

Входные данные
В первой строке заданы три целых числа: H, W и D (\(1\leq H,W \leq 300\), \(1 \leq D \leq H \cdot W\)).
В следующих H строках записано по W чисел A_i,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 целых числа: L_i и R_i (\(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

Динамическое программирование: один параметр Массивы Префиксные суммы(минимумы, ...)

✓ 5✗ 151 100средняяВойти и решать

Выбор цветов для букета#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 цветов.

Примеры

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

Бинарный поиск в массиве Префиксные суммы(минимумы, ...)

✓ 6✗ 331 000средняяВойти и решать

Комфортабельные коровы#38142

Пастбище Фермера Юрика может рассматриваться как огромная 2D-решётка ячеек (шахматная доска). Изначально пастбище пустое.

Фермер Юрик добавит N (\(1<=N<=10^5\)) коров на пастбище одну за другой. i-ая корова займёт ячейку (x_i,y_i), которая отличается от ячеек, занятых всеми другими коровами (\(0<=x_i,y_i<=1000\)).

Корова называется "комфортабельной", если она имеет ровно трёх соседей по горизонтали и вертикали. Комфортабельные коровы дают меньше молока, поэтому Фермер Юрик хочет добавлять коров пока нет комфортабельных (включая ту которую он добавит). Заметим, что добавляемые коровы не обязательно должны иметь координаты x и y в интервале \(0…1000\).

Для каждого i в интервале \(1…N\), выведите минимальное количество коров, которое он должен добавить, чтобы не осталось комфортабельных коров, если считать, что на пастбище находятся только коровы \(1…i\).

Входные данные
Первая строка содержит целое число N. Каждая из следующих N строк содержит по 2 разделённых пробелом целых числа (x, y), указывающих координаты ячейки с коровой.

Выходные данные
Минимальное количество коров, которое Фермер Юрик должен добавить, для каждого i в интервале \(1…N\), на отдельной строке.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	9 0 1 1 0 1 1 1 2 2 1 2 2 3 1 3 2 4 1	0 0 0 1 0 0 1 2 4	Для i=4, Фермер Юрик должен добавить корову в позицию (2,1), чтобы сделать корову в позиции (1,1) некомфортабельной. Для i=9, лучшее что Фермер может сделать - добавить коров в позиции (2,0), (3,0), (2,−1), (2,3).

Очередь Разбор случаев

✓ 2✗ 101 100средняяВойти и решать

Исправляем XML#34978

Формат XML является распространенным способом обмена данными между различными программами. Недавно программист Иванов написал небольшую программу, которая сохраняет некоторую важную информацию в виде XML-строки.

XML-строка состоит из открывающих и закрывающих тегов.

Открывающий тег начинается с открывающей угловой скобки (<), за ней следует имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка (>).
Примеры открывающих тегов: <a>, <dog>.

Закрывающий тег начинается с открывающей угловой скобки, за ней следует прямой слеш (/), затем имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка.
Примеры закрывающихся тегов: </a>, </dog>.

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

Пустая строка является корректной XML-строкой.
A и B — корректные XML-строки, то строка AB, получающаяся приписыванием строки B в конец строки A, также является корректной XML-строкой.
Если A — корректная XML-строка, то строка <X>A</X>, получающаяся приписыванием в начало A открывающегося тега, а в конец — закрывающегося с таким же именем, также является корректной XML-строкой. Здесь X — любая непустая строка из строчных букв латинского алфавита.

Например, представленные ниже строки:
<a></a>
<a><ab></ab><c></c></a>
<a></a><a></a><a></a>
являются корректными XML-строками, а такие строки как:
<a></b>
<a><b>
<a><b></a></b>
не являются корректными XML-строками.

Иванов отправил файл с сохраненной XML-строкой по электронной почте своему коллеге Петрову. Однако, к сожалению, файл повредился в процессе пересылки: ровно один символ в строке заменился на некоторый другой символ.
Требуется написать программу, которая по строке, которую получил Петров, восстановит исходную XML-строку, которую отправлял Иванов.

Входные данные: Входной файл содержит одну строку, которая заменой ровно одного символа может быть превращена в корректную XML-строку. Длина строки лежит в пределах от 7 до 1000, включительно. Строка содержит только строчные буквы латинского алфавита и символы «<» (ASCII код 60), «>»(ASCII код 62) и «/»(ASCII код 47).

Строка во входном файле заканчивается переводом строки.

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

Примеры

№	Входные данные	Выходные данные
1	<a></b>	<a></a>
2	<a><aa>	<a></a>
3	<a><>a>	<a></a>
4	<a/</a>	<a></a>

Стек

✓ 26✗ 1331 100средняяВойти и решать

Морской бой - 3#30781

Всем известна увлекательная игра «Морской бой». Сейчас играть в Морской бой можно не только с соседом по парте, но и с компьютером. Игра c компьютером ведется на прямоугольном поле произвольных размеров N×M, где N - количество строк, M - количество столбцов. Приближается чемпионат мира по Морскому бою. Планируется вести его трансляцию в режиме реального времени: демонстрировать карту с кораблями и выводить статистику: количество целых, подбитых и уничтоженных кораблей, находящихся на поле. Требуется написать программу для подсчета статистики.

Корабль на поле — это связанная фигура, стоящая из одной или нескольких рядом расположенных клеток, имеющих общую сторону. Корабли могут быть абсолютно любых форм и размеров!

Входные данные
Первая строка содержит два целых числа N и M (\(1<= N,M <= 10^3\)), разделённых пробелами. Это размеры игрового поля. Далее идут N строк по M символов - описание игрового поля. Английская буква 'X' обозначает подбитую клетку корабля, 'S' - не подбитую клетку корабля, '-' – свободное водное пространство.

Выходные данные
В ответе выведите через пробел три числа:
- количество целых кораблей;
- количество подбитых кораблей;
- количество уничтоженных кораблей.

Примеры

№	Входные данные	Выходные данные
1	3 8 ---SSS-- XX--S-X- X-S---S-	2 1 1

Очередь

✓ 269✗ 352800средняяВойти и решать

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

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

Мелехов тоскует, поэтому для каждого рейда он решил посчитать количество возможных отрядов по модулю \(10^9 + 7\). Однако Григорий постоянно находится в раздумьях о смысле жизни и поиске правды, поэтому он не может сконцентрироваться на расчетах и просит вас помочь.

Входные данные
В первой строке дано число n (\(1 <= n <= 10^5\)) – количество групп в банде Фомина.
Во второй строке дано n натуральных чисел a_i (\(1 <= a_i <= 10^6\)) – количество человек в i-ой группе.
В третьей строке дано число q – количество рейдов.
Далее дано q строк, в каждой из которых дано два числа – l_i и r_i (\(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

Быстрое возведение в степень Малая теорема Ферма Остатки Префиксные суммы(минимумы, ...)

✓ 11✗ 821 100средняяВойти и решать

Банды Фомина#30691

Входные данные

В первой строке дано число n (\(1 <= n <= 10^5\)) – количество групп в банде Фомина.

Во второй строке дано n натуральных чисел a_i (\(1 <= a_i <= 2\)) – количество человек в i-ой группе.

В третьей строке дано число q – количество рейдов.

Далее дано q строк, в каждой из которых дано два числа – l_i и r_i (\(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

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

✓ 29✗ 195900средняяВойти и решать

Рубка деревьев#29655

Чубатый учит Григория Мелехова выполнять баклановский удар шашкой. В качестве целей, они используют 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

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

✓ 39✗ 84800средняяВойти и решать

Тихий дон №2#29640

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

"Два указателя"Префиксные суммы(минимумы, ...)

✓ 94✗ 501800средняяВойти и решать

Тихий Дон №3#29638

Наталья Коршунова очень скучает по Григорию Мелехову и хочет вернуться к нему. Но, к сожалению, Григорий любит Аксинью, поэтому Наталья решила доказать любимому, что она лучше нее.

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

Григорий дает Наталье массив A, состоящий из n целых неотрицательных чисел. Затем он просит ее сделать q однотипных операций, заключающихся в следующем: "Даны числа l, r и k. Далее для каждого индекса i от l до r происходит подстановка числа k вместо числа A_i и считается побитовое исключающее “или” всех чисел на отрезке \([l;r]\), после чего на iое место опять возвращается число A_i".
Таким образом, происходит \(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.

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

✓ 66✗ 242800средняяВойти и решать

Modern Art#27215

Picowso - новый гений!
Picowso рисует особым способом. Она начинает на пустом холсте размером N×N ячеек, представленном решёткой из N×N нолей, где ноль обозначает пустую ячейку холста. Затем она рисует N² прямоугольников на холсте каждым из N² цветов последовательно пронумерованных 1…N². Например, она может начать рисовать прямоугольник цветом 2 и получится такой холст:

2 2 2 0

0 0 0 0

Затем она может нарисовать прямоугольник цветом 7:

2 2 2 0

2 7 7 7

0 0 0 0

А затем она может нарисовать маленький прямоугольник цветом 3:

2 2 3 0

2 7 3 7

2 7 7 7

0 0 0 0

Каждый прямоугольник имеет стороны, параллельные сторонам холста, и прямоугольник может быть таким большим как весь холст или таким маленьким как одна ячейка. Каждый цвет из 1…N² используется ровно один раз, хотя более поздние цвета могут полностью перекрыть более ранние цвета.

По заданному финальному состоянию холста определите сколько из N² цветов могли быть первым, использованным при рисовании.

ФОРМАТ ВВОДА:

Первая строка ввода содержит N, размер холста (1≤N≤1000). Следующие N строк описывают финальную картину на холсте, каждая строка содержит N целых чисел в интервале 0…N². Гарантируется, что картина была нарисована способом описанным выше, рисованием прямоугольников различных цветов.

ФОРМАТ ВЫВОДА:

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

Ввод	Вывод
4 2 2 3 0 2 7 3 7 2 7 7 7 0 0 0 0	14

В этом примере цвет 2 мог быть использован первым. Цвет 3 был использован после цвета 7, а цвет 7 был использован после цвета 2. Поскольку мы не видим других цветов, мы делаем вывод, что они также могли быть использованы первыми (а потом перекрашены).

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

✓ 2✗ 101 100средняяВойти и решать