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

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

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

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

✓ 264✗ 468600лёгкаяВойти и решать

Два одинаковых массива#28345

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

Входные данные
В первой строке записано натуральные числа N и M– количество элементов первого и второго массива соответственно, (1 <= N, M <= 10⁸). В следующих двух строках записаны элементы массива A и B. Во второй строке - элементы массива A, в третьей - элементы массива B. Все элементы массива неотрицательные числа, не превышающие 10¹⁸.

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

Примеры

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

"Два указателя"Хеш

✓ 807✗ 1 970500лёгкаяВойти и решать

Одномерные массивы. Введение#25971

В программе измените объявление массива таким образом, чтобы массив состоял из 30 элементов.

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

✓ 3 390✗ 1 568100лёгкаяВойти и решать

Легкая, вариант-2#24735

На складе хранятся ящики разных цветов и размеров. Каждый цвет и каждый размер имеют свой порядковый номер в информационной системе.

Перед отправкой ящики упаковывают и сортируют. Упаковка и сортировка ящиков неэффективна и происходит следующим образом:

Ящик под номером i поступает на склад.
Ищется стопка, в которой хранятся ящики с размером, равным размеру i-го. Если такой стопки нет, формируется новая стопка.
Поступающий ящик помещается наверх найденной или сформированной стопки.
Если в какой-либо стопке оказывается два верхних ящика одного цвета, то они запаковываются и отправляются адресату.

Отправка продолжается до тех пор, пока не будут обработаны все поступающие на склад ящики.

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

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

В первой находятся три натуральных числа n, m, k (1 ≤ n, m, k ≤ 100) — количество ящиков, поступающих на склад, количество различных размеров и количество различных цветов соответственно.
В каждой из следующих n строк находятся по два натуральных числа x_i и y_i (1 ≤ x_i ≤ m; 1 ≤ y_i ≤ k) — номер размера и номер цвета ящика, который поступит i-м на склад.

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

Требуется вывести одно число — сколько ящиков будут отправлены.

Пример входных и выходных данных

Вывод	Ввод
5 2 1 1 1 2 1 1 1 2 1 1 1	4
5 1 2 1 1 1 2 1 1 1 2 1 1	0

Задачи на моделирование Очередь реализация

✓ 73✗ 62600лёгкаяВойти и решать

Легкая, вариант-1#24734

Ящик под номером i поступает на склад.
Ищется стопка, в которой хранятся ящики с размером, равным размеру i-го. Если такой стопки нет, формируется новая стопка.
Поступающий ящик помещается наверх найденной или сформированной стопки.
Если в какой-либо стопке оказывается два верхних ящика одного цвета, то они запаковываются и отправляются адресату.

Отправка продолжается до тех пор, пока не будут обработаны все поступающие на склад ящики.

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

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

В первой строке находятся три натуральных числа n, m, k (1 ≤ n, m, k ≤ 100) — количество ящиков, поступающих на склад, количество различных размеров и количество различных цветов соответственно.
В каждой из следующих n строк находятся по два натуральных числа x_i и y_i (1 ≤ x_i ≤ m; 1 ≤ y_i ≤ k) — номер размера и номер цвета ящика, который поступит i-м на склад.

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

Требуется вывести одно число — сколько ящиков останутся на складе, после выполнения отправки.

Пример входных и выходных данных

Ввод	Вывод
5 2 1 1 1 2 1 1 1 2 1 1 1	1
5 1 2 1 1 1 2 1 1 1 2 1 1	5

Очередь реализация

✓ 76✗ 45500лёгкаяВойти и решать

Дерево отрезков#23581

Корвин и Блейз готовятся ко вторжению в Амбер, чтобы свергнуть Эрика. Для этого им нужно собрать армию. В мире, где они находятся есть n поселений, расположенных в линию из-за особенностей местности. Известно, что в первом поселении есть a₁ воинов, во втором - a₂, в i-ом - a_i, в n-ом - a_n.

Иногда Корвин и Блейз узнают, что в a_i поселении иное количество воинов, чем предполагалось. Корвин и Блейз спрашивают вас m раз, какое максимальное количество воинов, имеющееся в каком-либо поселении может предоставить наибольшее число воинов. Помогите им определить это.

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

В первой строке на вход подаются числа n и m (1 <= n, m <= 100000) - число поселений и число запросов.

Во второй строке находятся n чисел a₁, a₂, ..., a_n (1 <= a_i <= 1000) - количество воинов в поселениях.

В следующих m строках находятся числа t, l и r (1 <= l <= r <= n), (0 <= t <= 1) - если t равно 0, то l и r - границы запросов. Иначе l - номер города, а r - новая информация.

Выходные данные
На i-той строке выведите ответ на i-тый запрос, если t_i=0, иначе выведите "-1".

Примеры

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

Дерево отрезков, RSQ, RMQ

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

Раскраска#21884

Рисунок задан в виде матрицы A, в которой элемент A[y][x] определяет цвет пикселя на пересечении строки y и столбца x. Перекрасить в цвет 2 одноцветную область, начиная с пикселя (x0,y0).

Входные данные
В первой строке задается размер квадратной матрицы n (\(0<n<10\)). Во второй строке заданы координаты точки (x0, y0) - два числа через пробел (0 <= x0, y0 < n) . Далее идут n строк по n неотрицательных чисел в каждой через пробел (каждое число не больше 10).

Выходные данные
Вывести получившуюся после перекраски матрицу.

Примеры

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

Источник: К.Ю. Поляков. Учебник. Информатика.

Очередь

✓ 706✗ 1 263600лёгкаяВойти и решать

Вычисление арифметических выражений#21882

Постфиксная запись представляет собой такую запись алгебраического выражения, в которой сначала записываются операнды, а затем – знак операции. Например, для выражения a + b * c постфиксная запись будет a b c * +.

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

Входные данные
На вход подается символьная строка. Знак / в записи означает целочисленное деление.

Выходные данные
Выведите на экран результат выражения.

Примеры

№	Входные данные	Выходные данные
1	5 3 + 7 4 - *	24

Разбор выражений Стек

✓ 864✗ 986500лёгкаяВойти и решать

Математическое выражение#21878

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

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

Выходные данные
Если скобки расставлены верно, то вывести на экран слово Yes, в противном случае - No и количество неправильно расставленных скобок (скобка считается неправильно расставленной, если у нее нет пары).

Примеры

№	Входные данные	Выходные данные
1	7-((X*((X+Y)/(J-3))+Y)/(4-2.5))	Yes
2	(a-c/(d)	No. Incorrect brackets = 1

реализация Стек

✓ 595✗ 1 569600лёгкаяВойти и решать

Скобки#21877

Напишите программу, которая проверяет правильность расстановки скобок в арифметическом выражении. Используются скобки трёх типов: ( ), [ ] и { }.

Входные данные
На вход подается строка.

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

Примеры

№	Входные данные	Выходные данные
1	(5+7)[5+{(4+3)[9-6]+7}-8]	Yes
2	[(2+3)	No

Задача на реализацию Стек

✓ 1 271✗ 2 745500лёгкаяВойти и решать

HASH#21822

Программисту Васе не повезло - вместо отпуска его послали в командировку на научную конференцию. "Надо повышать уровень знаний", - сказал начальник, "Важная конференция по криптографии, проводится во Франции - а там шифровали еще во времена Ришелье и взламывали чужие шифры еще во времена Виета."

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

Один из докладчиков, в очередной раз пытаясь разгадать шифры Бэкона, выдвинул гипотезу, что ключ к тайнам Бэкона можно подобрать, проанализировав все возможные подстроки произведений Бэкона. "Но их же слишком много!" - вслух удивился Вася. "Нет, не так уж и много!" - закричал докладчик, - "Подсчитайте, и вы сами убедитесь!"

Тем же вечером Вася нашел в интернете полное собрание сочинений Бэкона. Он написал программу, которая переработала тексты в одну длинную строку, выкинув из текстов все пробелы и знаки препинания. И вот теперь Вася весьма озадачен - а как же подсчитать количество различных подстрок этой строки?

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

На входе дана непустая строка, полученная Васей. Строка состоит только из строчных латинских символов. Ее длина не превосходит 2000 символов.

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

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

Примеры

№	Входные данные	Выходные данные
1	aaba	8

Хеш

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

Минимальное остовное дерево c с данным ребром#21748

Требуется найти в связном графе остовное дерево минимального веса в котором есть данное ребро.

Формат файла входных данных:

Первая строка входного файла содержит два натуральных числа N, M - количество вершин и ребер графа соответственно. Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя натуральными числами Bi, Ei, Wi номера концов ребра и его вес соответственно (1 <= Bi, Ei <= N, 0 <= Wi <= 2^32-1. N <= 10, M <= 10). В последней строке вводится данное ребро B, E, W.

Формат файла выходных данных:

Единственная строка выходного файла должна содержать одно натуральное число - вес минимального остовного дерева c данным ребром.

Ввод:

4 4

1 2 1

2 3 2

3 4 5

4 1 4

1 4 7

Вывод:

Система непересекающихся множеств

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

Длина пути#19885

В неориентированном графе требуется найти длину кратчайшего пути между двумя вершинами.

Формат входных данных
В первой строке входных данных записано число N - количество вершин в графе (1 <= N <= 100). Далее с новой строки записана матрица смежности (0 обозначает отсутствие ребра, 1 - наличие ребра). В последней строке записаны номера двух вершин - начальной и конечной.

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

Обход в ширину Очередь

✓ 1 225✗ 3 024500лёгкаяВойти и решать

Наибольшее произведение#18715

Дано N целых чисел. Требуется выбрать из них три таких числа, произведение которых максимально.

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

На вход подается сначала число N - количество чисел в последовательности (\(3<=N<=100\)).
Далее идет сама последовательность: N целых чисел, по модулю не превышающих 1000.

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

Выведите три искомых числа в любом порядке.

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

Примеры

№	Входные данные	Выходные данные
1	9 3 5 1 7 9 0 9 -3 10	9 10 9
2	3 -5 -300 -12	-5 -300 -12

Очередь

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