Информатика

15 724 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Банды Фомина#30691

Банда Фомина состоит из 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
Префиксные суммы(минимумы, ...)
✓ 29✗ 195900средняяВойти и решать
Сложная сортировка массива структур#30690
Дан список людей состоящих из фамилии и имени. Напишите программу, которая отсортирует список по фамилиям в возрастающем лексикографическом порядке. Если фамилии совпадают, то отсортировать по имени.
 
Входные данные
Сначала задано число N - количество людей в списке (1<= N <= 100). Далее через пробел записаны N фамилий и мен.
 
Выходные данные
Необходимо вывести массив отсортированный по фамильно в возрастающем лексикографическом порядке, при совпадении фамили, сортировать по имени.
 
Примеры
№ Входные данные Выходные данные
1 3
Sidorov Petr
Ivanov Ivan
Ivanov Anton
Ivanov Anton
Ivanov Ivan
Sidorov Petr
Сортировка записей
✓ 113✗ 106500лёгкаяВойти и решать
Сортировка вектора: Начало#30686
Дана последовательность, состоящая из целых чисел. Напишите программу, которая создает и сортирует массив по убыванию.
 
Входные данные
Сначала задано число N — количество элементов в массиве (1<=N<=100). Далее через пробел записаны N чисел - элементы массива. Массив состоит из целых чисел.
 
Выходные данные
Необходимо вывести массив, отсортированный по убыванию.
 
Примеры
№ Входные данные Выходные данные
1 5
4 56 23 67 100		 100 67 56 23 4
Массивы
✓ 284✗ 157300лёгкаяВойти и решать
Отрезки#30685
Имеется прямая, покрашенная в белый цвет. На нее добавляют n черных отрезков один за другим.
Определите количество компонент связности из черных отрезков (то есть количество черных отрезков в объединении) после каждого добавления отрезка.
В частности, считайте, что если один отрезок заканчивается в точке x, а другой отрезок начинается в точке x, то эти два отрезка лежат в одной компоненте связности.
 
Входные данные
В первой строке следует целое число n (1 ≤ n ≤ 200 000) — количество отрезков.
i-я из следующих n строк содержит два целых числа li и ri (1 ≤ li < ri ≤ 109) — координаты левого и правого концов отрезка номер i. Отрезки перечислены в порядке их добавления на белую прямую.
 
Выходные данные
Выведите n целых чисел — количество компонент связности из черных отрезков после каждого добавления отрезка.

 
Примеры
№ Входные данные Выходные данные
1
3
1 3
4 5
2 4
 1 2 1
2
9
10 20
50 60
30 40
70 80
90 100
60 70
10 40
40 50
80 90
 1 2 3 4 5 4 3 2 1

 
 
Множества
✓ 54✗ 164900средняяВойти и решать
Симметричная запись из цифр#30680

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

Если требуемую строку составить невозможно, то программа должна вывести на экран число 0, а если возможно, то вывести число 1.

Входные данные
На вход программе подаётся натуральное число N (\(N <= 100000\)), а затем N натуральных чисел, каждое из которых не превышает 10000.

Пример входных данных
3
13
22
32

Пример выходных данных для приведённого примера входных данных:
0
Из цифр D, 1, 6, 2, 0 нельзя составить симметричную строку.

Пример входных данных:
4
186
68
171
14

Пример выходных данных для приведённого примера входных данных:
1
Из цифр A, B, 4, 4, A, B, D можно составить симметричную строку

Напишите эффективную по времени и по памяти программу, которая решает поставленную задачу.
ЕГЭ - вычислительные задачи
✓ 561✗ 627600лёгкаяВойти и решать
Сумма на отрезке#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лёгкаяВойти и решать
Финал#30658
Ежегодно в Санкт-Петербурге, Барнауле и некоторых городах ближнего зарубежья проходят соревнования по программированию. Эти соревнования проходят в рамках студенческого чемпионата мира по программированию, организованного одной из самых авторитетных ассоциаций АСМ (Association for Computing Machinery). На этих соревнованиях проходит отбор команд с Северо-Восточного Европейского Региона NЕЕRС (North-Eastern European Regional Contest). Ежегодно перед организаторами соревнований встает проблема определения команд, которые будут приглашены к участию в финале чемпионата мира по программированию. По новым правилам в финал проходят не более N команд, представляющих NEERC. Кроме этого, от одного вуза не может проходить более чем k команд. При этот из всех таких множеств выбирается то, в котором сумма мест занятых этими командами в полуфинальных соревнованиях минимальная возможная. Ваша задача по итоговому протоколу полуфинальных соревнований и числам N и k определить, какие команды будут приглашены к участию в финале чемпионата мира.
 
Входные данные
В первой сроке входного файла находится три натуральных числа Р (1 ≤ P ≤ 100000) — количество команд, принявших участие в полуфинале, N (1 ≤ N ≤ P ) и k (1 ≤ k ≤ P ) . В следующих P строках, по одному в строке перечислены названия университетов, команды которых заняли соответствующие места. Название университета содержит строчные и прописные латинские буквы и пробелы. Длина названия университета не превышает 30 символов. В следующей строке перечислены номера команд соответствующих университетов. Таким образам если название университета записано в i -той строке (2 ≤ i ≤ P + 1) , то эта команда заняла i - 1 место на полуфинале и имеет номер, записанный на i - 1 месте в P + 2 строке.
 
Выходные данные
В выходной файл выведите названия команд, приглашенных к участию в финале чемпионата мира по программированию, упорядоченных по месту, занятому на полуфинале. В качестве названия команды выведите название университета и через пробел #номер команды.
 
Пример
№ Входные данные Выходные данные
1
9 5 2
Fantasy University
Crazy University
Fantasy University
Fantasy University
Very Good U
Good U
Very Good U
Crazy University
Good U
1 1 2 3 2 1 1 2 2
Fantasy University #1
Crazy University #1
Fantasy University #2
Very Good U #2
Good U #1
Словари
✓ 366✗ 663800средняяВойти и решать
Cart Sorting#29658
У  Акакия есть колода, состоящая из n карт. На каждой карте написано ровно одно целое число от 1 до 100 000. Возможно, что на некоторых картах написаны одинаковые числа.
Акакий решил отсортировать все карты в колоде. Для этого он по очереди берёт одну верхнюю карту из колоды и если число, написанное на ней, равно минимальному среди всех оставшихся чисел в колоде, он откладывает эту карту в сторону. В противном случае, Акакий кладёт эту карту вниз колоды и берёт сверху колоды следующую карту. Процесс заканчивается, когда в колоде не останется карт. Можно считать, что Акакий в любой момент времени знает минимальное число, записанное на какой-то из оставшихся в колоде картах, но не знает, где эта карта (или карты) находится в колоде.
Перед вами стоит задача определить суммарное количество раз, которое Акакий посмотрит верхнюю карту из колоды.
 
Входные данные
В первой строке следует целое положительное число n (1 ≤ n ≤ 100 000) — количество карт в колоде.
Во второй строке следует последовательность из n целых положительных чисел a1, a2, ..., an (1 ≤ ai ≤ 100 000), где ai равно числу, написанному на i-й сверху карте из колоды.
 
Выходные данные
 
Выведите суммарное количество раз, которое Акакий посмотрит верхнюю карту из колоды.

Ввод Вывод
4
6 3 1 2
 7
1
1000		 1
7
3 3 3 3 3 3 3		 7


Примечание
В первом примере Акакий посмотрит сначала карту с числом 6, положит ее вниз колоды, затем карту с числом 3, также положит ее вниз колоды, и затем карту с числом 1. Он отложит карту с числом 1, так как на ней написан минимальное число из оставшихся в колоде. После этого карты в колоде будут лежать в порядке [2, 6, 3] сверху вниз. После этого Акакий посмотрит верхнюю карту с числом 2 и отложит её. После этого карты в колоде будут лежать в порядке [6, 3] сверху вниз. Затем Акакий посмотрит карту с числом 6, положит ее вниз колоды, а затем карту с числом 3, которую отложит. После этого в колоде останется одна карта с числом 6, которую Акакий посмотрит и отложит. Таким образом, Акакий посмотрит 7 карт.
 
(с) Курбатов Е., 2018

Декартово дерево
✓ 1✗ 31 100средняяВойти и решать
Рубка деревьев#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средняяВойти и решать
Поиск числа на отрезке#29653

Дан массив a длины n (\(1 <= n <= 10^6\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 500\)) запросов вида +, l, r, k (\(1 <= l <= r <= n\), \(-10^9 <= k <= 10^9\)) и запросов вида ?, l, r, k (\(1 <= l <= r <= n\), \(-10^9 <= k <= 10^9\)).

В первом случае нужно добавить к числам на отрезке от l до r включительно, число k.
Во втором случае нужно вывести 1, если на отрезке от l до r включительно, есть число k, иначе вывести 0.

Элементы нумеруются с 1 до n.

Гарантируется, что после любого запроса любой элемент массива a лежит в диапазоне от \(-10^9\) до \(10^9\) включительно.

 

Примеры
№ Входные данные Выходные данные
1
5
1 2 1 1 3
3
? 1 4 3
+ 2 3 2
? 1 4 3
 0
1
sqrt декомпозиция
✓ 6✗ 311 000средняяВойти и решать
Умножение на отрезке#29652

Дан массив a длины n (\(1 <= n <= 2 \cdot 10^6\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 500\)) запросов вида *, l, r, k (\(1 <= l <= r <= n\), \(0 <= k <10\)) и запросов вида ?, i (\(1 <= i <= n\)).

В первом случае нужно умножить числа на отрезке от l до r включительно на k.

Во втором случае нужно вывести число, стоящее на позиции i.

Элементы нумеруются с 1 до n.

 

Примеры
№ Входные данные Выходные данные
1
5
1 1 1 1 1
3
? 3
* 2 3 9
? 3
 1
9
sqrt декомпозиция
✓ 15✗ 66800средняяВойти и решать
Максимум на матрице#29651
Дана матрица a размером \(n \cdot n\) (\(1 <= n <= 1000\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 1000\)) запросов вида x1, y1, x2, y2 (\(1 <= x_1 <= n\), \(1 <= y_1 <= n\), \(x_1 <= x_2 <= n\), \(y_1 <= y_2 <= n\)).
На каждый запрос нужно вывести максимальный элемент в подматрице с координатами краёв x1, y1 и x2, y2.

 

Примеры
№ Входные данные Выходные данные
1
4
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
1
1 1 3 4
 6
sqrt декомпозиция
✓ 7✗ 251 000средняяВойти и решать
Сумма на отрезке - 2#29650

Дан массив a длины n (\(1 <= n <= 2 \cdot 10^6\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 500\)) запросов вида t, l, r (\(0 <= t <= 1\), \(1 <= l <= r <= n\)).

Если \(t = 0\), то на запрос нужно вывести сумму чисел на отрезке от l до r включительно. Если \(t = 1\), то элементу с номером l присваивается значение r. Элементы нумеруются с 1 до n. 

 

Примеры
№ Входные данные Выходные данные
1
5
1 2 3 4 5
4
0 1 2
1 1 5
0 1 2
0 1 1
 3
7
5
sqrt декомпозиция
✓ 19✗ 52800средняяВойти и решать
Сумма на отрезке - 1#29649

Дан массив a длины n (\(1 <= n <= 2 \cdot 10^6\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 500\)) запросов вида l, r (\(1 <= l <= r <= n\)).

На каждый запрос нужно вывести сумму чисел на отрезке от l до r включительно. Элементы нумеруются с 1 до n.

 

Примеры
№ Входные данные Выходные данные
1
4
1 2 3 4
2
1 4
1 1
 10
1
2
5
5 5 5 5 5
1
5 5
 5
sqrt декомпозиция
✓ 26✗ 252900средняяВойти и решать
29648#29648
Дано число n, n  100 . Создайте массив n×n и заполните его по следующему правилу:
- числа на диагонали, идущей из правого верхнего в левый нижний угол, равны 1; 
- числа, стоящие выше этой диагонали, равны 0;
- числа, стоящие ниже этой диагонали, равны 2.

Входные данные
Программа получает на вход число n.
 
Выходные данные
Необходимо вывести  полученный массив. Числа разделяйте одним пробелом.

Двумерные массивы
✓ 0✗ 6—Войти и решать
Запросы в массив#29643
Вам нужно реализовать структуру данных на базе массива, которая сможет отвечать на данные типы запросов:

0 - вывести размер массива и знак перехода на новую строку;
1 x - добавить в конец массива число x;
2 - удалить последний элемент массива;
3 x y - вставить число y между элементами массива x и x + 1;
4 x - удалить элемент №x;
5 - вывести все элементы массива в порядке их следования в нем через пробел. В конце выведите знак перехода на новую строку;
6 x - изменить размер массива на x. Если x меньше текущего размера массива, то все элементы, начиная с элемента №x отбрасываются. Если x больше текущего размера массива, то появившиеся элементы массива будут равны 0.
 
Формат входных данных
- в первой строке содержится число N (\(1 <= n <= 100\));
- в следующих N строках содержатся запросы в формате, записанном в условии.
 
Формат выходных данных
Выведите ответы на запросы типа 0 и 5.
Standard Template Library
✓ 340✗ 1 216700средняяВойти и решать
Тихий Дон №1#29641
В мирное время казаки занимаются сельским хозяйством. Пантелей Прокофьевич Мелехов выращивает специальные математические овощи, которые растут по очень странным правилам: у каждого семечка i этих овощей есть значение урожайности ai, а урожайностью всей грядки является произведение урожайностей всех семян, посаженных на ней. У Мелехова есть N семян. Помогите ему выбрать из этих семян несколько так, чтобы при посадке этих семян урожайность грядки была максимальна.
 
Входные данные:
В первой строке содержится число N (1 <= N <= 15)
Во второй - N чисел ai, возможно вещественных (|ai| < 10)
 
Выходные данные:
Выведите максимальную урожайность грядки с точностью не менее 6 знаков после запятой, которой можно добиться с данным набором семян. Гарантируется, что оно больше 1.
 
Ввод Вывод
5
2.0 -1.2 4.7 -2.9 -1.1
 32.712000

(с) Григорьев Е., 2018
Битовые операции
✓ 52✗ 93600лёгкаяВойти и решать
Тихий Дон №3#29638
Наталья Коршунова очень скучает по Григорию Мелехову и хочет вернуться к нему. Но, к сожалению, Григорий любит Аксинью, поэтому Наталья решила доказать любимому, что она лучше нее.
Для этого Наталья отправилась к Григорию и заявила, что она может решить любую задачу, какую бы он ни предложил. Мелехов принял вызов.
 
Григорий дает Наталье массив 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.
 
Префиксные суммы(минимумы, ...)
✓ 66✗ 242800средняяВойти и решать
Интернет-магазин#29635
Дана база данных о продажах некоторого интернет-магазина. Каждая строка входного файла представляет собой запись вида:
Покупатель товар количество,
где Покупатель — имя покупателя (строка без пробелов), товар — название товара (строка без пробелов), количество — количество приобретенных единиц товара.
 
Создайте список всех покупателей, а для каждого покупателя подсчитайте количество приобретенных им единиц каждого вида товаров.
 
 
Входные данные
В первой строке входного файла содержится число N (\(1<=N<=100000\)) —количество записей содержащихся в данной базе данных. Вводятся сведения о покупках в указанном формате.
 
Выходные данные 
Выведите список всех покупателей в лексикографическом порядке, после имени каждого покупателя выведите двоеточие, затем выведите список названий всех приобретенных данным покупателем товаров в лексикографическом порядке, после названия каждого товара выведите количество единиц товара, приобретенных данным покупателем. Информация о каждом товаре выводится в отдельной строке.
 
 
Пример
№ Входные данные Выходные данные
1
6
Ivanov paper 10
Petrov pens 5
Ivanov marker 3
Ivanov paper 7
Petrov envelope 20
Ivanov envelope 5
Ivanov:
envelope 5
marker 3
paper 17
Petrov:
envelope 20
pens 5
Словари
✓ 746✗ 991600лёгкаяВойти и решать
Поделиться
Класснуть