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

Гармония#60824

Совсем недавно Васе на день рождения подарили строку, состоящую только из символов «0» и «1». Обрадованный этим подарком, он тут же начал эту строку изучать — искать в ней гармоничные части. Для начала Васю интересует только количество различных непустых гармоничных подстрок. А поскольку подарок оказался слишком большим, мальчик решил обратиться за помощью к вам. Помогите Васе!
В понимании Васи, строка является гармоничной, если и символов 0, и символов 1 в ней чётное количество.
Подстрокой строки s называется строка, полученная из s выкидыванием нескольких символов с начала и с конца (возможно, нуля или всех). Так, строка «12» является подстрокой строки «123», а строка «13» — нет. Подстроки считаются одинаковыми, если у них совпадает количество удалённых символов с начала и с конца.

Формат входных данных
В первой строке дано одно число n — длина подарка (1 ≤ n ≤ 2 · 10⁵ ). Во второй строке дана строка s длины n — Васин подарок. Гарантируется, что s состоит только из нулей и единиц.
Формат выходных данных
Выведите единственное число — количество различных гармоничных подстрок в s.
Обратите внимание, что значение ответа в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64- битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

Замечание
В первом примере из условия подходят следующие подстроки (выделены жирным): 001100, 001100, 001100, 001100, 001100, 001100, 001100.

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

✓ 7✗ 51 200средняяВойти и решать

Два мусоровоза#43721

На каждом километре кольцевой автодороги с двусторонним движением установлены контейнеры для мусора. Длина кольцевой автодороги равна 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

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

✓ 0✗ 761 400средняяВойти и решать

Бинарная сортировка#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⁵.

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

Примеры

№	Входные данные	Выходные данные
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.

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

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

Чтение вслух#39673

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

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

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

Примеры:

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

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

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

Достаточно зеленого#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++).

Входные данные
Первая строка содержит 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

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

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

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

Кот Гусь подготовил для Ника Фьюри прямоугольную таблицу a размера \(n \cdot m\), содержащую числа от 0 до p−1. Ник Фьюри сразу понял, что каждое число в этой таблице выбрано случайно равновероятно от 0 до p−1, независимо от остальных.

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

Формально, вам необходимо найти такие \(1 <= i_1 <= i_2 <= n\), \(1 <= j_1 <= j_2 <= m\), что сумма a_x,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-й строке равно a_i,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

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

✓ 8✗ 1791 200средняяВойти и решать

Падающее домино#27042

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

Для своей новой идеи он использует костяшки не только длиной 2, но и более длинные (и более короткие). Все костяшки выстраиваются в одну линию на расстоянии 1, а цель игры опрокинуть все костяшки толкнув наименьшее количество костяшек.

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

Формат входных данных

В первой строке записано натуральное число N (0 <= N <= 1 000 000) количество костяшек. Во второй строке записано N натуральных чисел H_i (1 <= Hi <= 1 000 000) высоты костяшек.

Формат выходных данных

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

В следующих M строках выведите описание костяшек, которые необходимо толкнуть: номер костяшки (нумерация начинается с единицы и идет слева-направо), а также направление толчка: букву L для толчка влево и R для толчка вправо. Номер костяшки и букву разделяйте пробелом.

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

Система оценки

Решения, верно работающие при N <= 1000, будут набирать не менее половины баллов.

Ввод	Вывод
6 1 2 1 4 1 3	1 6 L
7 1 2 4 1 2 3 2	2 3 R 2 L

Замечание

В первом примере последняя костяшка толкается влево, опрокидывая костяшки с номерами 4 и 5 (их высоты 4 и 1 соответственно). Костяшка номер 4 также падает налево и опрокидывает костяшки с номерами 1, 2 и 3.

Во втором примере костяшка номер 3 толкается вправо, опрокидывая костяшки номер 4, 5 и 6.

Костяшка номер 6 также падает вправо и опрокидывает костяшку номер 7. После этого костяшка

номер 2 толкается влево и опрокидывает костяшку номер 1.

Префиксные суммы(минимумы, ...)Разбор случаев Структуры данных

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

Украшение ёлки – 2#24638

И вот вновь наступил Новый Год, и Васе снова понадобилось наряжать ёлку. Но, памятуя о своих прошлогодних неудачах (Вы о них знаете, если решали прошлогодний контест), он купил в магазине брендовые ударопрочные шарики. К сожалению, на ёлку в результате денег почти не осталось, и её пришлось покупать у какого-то индуса. Поэтому ёлка имеет форму полного двоичного дерева глубины N – на верхушке только одна ветка, и под каждой веткой, кроме самых нижних, снизу растёт ровно две. В самом низу, соответственно, под ветками только Васин немытый пол.

Но когда Вася приступил к украшению, он понял, что совершил страшную ошибку. Ударопрочные шарики были одноцветными и скучными, поэтому Вася не мог развесить их как попало, как он делал это раньше. Пришлось ему разрабатывать алгоритм украшения. Для начала он соотнёс каждому цвету его индекскрасоты – параметр от 0 до 10⁹. Чем он больше, тем более красивым кажется Васе шар этого цвета. Потом он случайным образом развесил шарики у пола (на каждую ветку Вася всегда вешает только один шар). Для всех остальных веток Вася смотрел на их нижних соседей, определял, какой из висящих на этих ветках шариков красивее, и вешал на эту ветку точно такой же.

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

Нижние ветви пронумерованы от 1 до 2^(N- 1), более верхним Вася из лени решил номера не давать. Вася подаёт на вход два вида запросов. В первом он заменяет какой-либо шар в нижнем уровне с номером k на шар цвета c, и хочет узнать, на скольких слоях веток (кроме нижнего) ему придётся перевесить шары, чтобы ёлка по-прежнему подходила под описанный выше алгоритм. Во втором он хочет узнать цвет самого красивого шара в секторе от l до r. К сектору относятся все ветки нижнего слоя с номерами от l до r включительно, а также все находящиеся над ними ветки.То есть, если N = 3, то к секторуот 1 до 2 относятся ветки 1 и 2, а также третья ветка, находящаяся между ними чуть выше.

Формат ввода

В первой строке задана глубина ёлки N (N<= 15) и количество запросов M (M<= 10⁷). Во второй строке задана первоначальная развеска нижних шариков, представленная их индексами красоты. В следующих M строках заданы запросыдвух типов (первый обозначен цифрой 1, а второй, как ни странно, 3). Описание запросов дано выше.

Формат вывода

Нужно вывести Mстрок, содержащих ответы на запросы.

Пример

Ввод:

4 5

1 1 2 3 100 7 11 3

3 1 8

3 2 4

1 5 4

3 1 8

1 5 9

Вывод:

100

Дерево отрезков, RSQ, RMQ Префиксные суммы(минимумы, ...)

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