Информатика

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

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

Торги проходят в течении \(n\) дней, всего на рынке представлены акции \(m\) компаний, цены акций компании фиксированы в течении одного дня. Сделки бывают двух типов:

  • Купить \(x\) акций компании \(comp\)

  • Продать все акции компании \(comp\)

За каждую сделку надо заплатить 1% комиссии. Например, если купить 10 акций по 300 рублей, то суммарно заплатить придется 3030 рублей. Если же продавать 10 акций стоимостью 300 рублей каждая, то за них можно получить 2970 рублей.

Прибылью с продажи будем считать разность полученных при продаже денег и суммарно потраченных денег при покупках. Например, если 10 акций были куплены по 300 рублей, а затем еще 5 акций были куплены по 400 рублей, то в случае продажи по стоимости 500 прибыль составит: \(15 \cdot 500 \cdot 0.99 - (10 \cdot 300 \cdot 1.01 + 5 \cdot 400 \cdot 1.01) = 7425 - (3030 + 2020) = 2375\) рублей. При этом, акции могут быть проданы в убыток (за меньшую стоимость, чем были куплены), тогда прибыль с продажи будем считать отрицательной.

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

Вам даны \(k\) событий покупки/продажи. Необходимо найти минимальную суммарную прибыль среди всех моментов времени.

Входные данные
В первой строке входных данных содержится одно целое число \(t\) — число тестовых наборов (\(1 \le t \le 30\)).

Затем следуют \(t\) тестовых наборов. Каждый тестовый набор описывается следующим образом:

В первой строке тестового набора содержатся три целых числа \(n\), \(m\) и \(k\) — число дней, в которые проходят торги, число компаний на рынке и число событий, соответственно (\(1 \le n, m \le 100\), \(1 \le k \le 1000\)).

В следующих \(m\) строках записаны названия компаний и \(n\) чисел — стоимости акций компании в рублях в каждый из дней торгов. Названия компаний состоят из не более чем \(10\) строчных букв латинского алфавита и попарно различны. Стоимости акций — целые числа в диапазоне от \(1\) до \(10^5\) включительно.

В следующих \(k\) строках заданы события покупки/продажи в хронологическом порядке. Событие покупки задается в формате <день> buy <число акций> <название компании>, а событие продажи задается в формате <день> sell <название компании>. При этом <день> — целое число от \(1\) до \(n\), а <число акций> — целое число от \(1\) до \(1000\). Гарантируется, что все события следуют в порядке неубывания дней и корректны, а именно нет продаж некупленных акций и покупок акций, которых нет на рынке.

Выходные данные
Для каждого тестового набора выведите в отдельной строке минимальную прибыль среди всех моментов времени, с относительной или абсолютной погрешностью не более \(10^{-4}\).


Примечание

В первом тестовом наборе изначально до продаж суммарная прибыль равна \(0\), после первой продаже суммарная прибыль становится \(2375\) (случай разобран в примере).

Во втором тестовом наборе промежуточные прибыли равны \(0\), \(-11.11\) (акция продана дороже, но комиссия больше разницы) и \(1948.89\).

В третьем тестовом наборе промежуточные прибыли равны \(0\) и \(-2080\).

В четвертом тестовом наборе промежуточные прибыли равны \(0\) и \(979.9\), деньги потраченные на непроданные акции не учитываются.

Задача на реализациюЗадачи на моделирование
✓ 1✗ 1—Войти и решать
Биржа#49775

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

Торги проходят в течении \(n\) дней, всего на рынке представлены акции \(m\) компаний, цены акций компании фиксированы в течении одного дня. Сделки бывают двух типов:

  • Купить \(x\) акций компании \(comp\)

  • Продать все акции компании \(comp\)

За каждую сделку надо заплатить 1% комиссии. Например, если купить 10 акций по 300 рублей, то суммарно заплатить придется 3030 рублей. Если же продавать 10 акций стоимостью 300 рублей каждая, то за них можно получить 2970 рублей.

Прибылью с продажи будем считать разность полученных при продаже денег и суммарно потраченных денег при покупках. Например, если 10 акций были куплены по 300 рублей, а затем еще 5 акций были куплены по 400 рублей, то в случае продажи по стоимости 500 прибыль составит: \(15 \cdot 500 \cdot 0.99 - (10 \cdot 300 \cdot 1.01 + 5 \cdot 400 \cdot 1.01) = 7425 - (3030 + 2020) = 2375\) рублей. При этом, акции могут быть проданы в убыток (за меньшую стоимость, чем были куплены), тогда прибыль с продажи будем считать отрицательной.

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

Вам даны \(k\) событий покупки/продажи. Необходимо найти максимальную суммарную прибыль среди всех моментов времени.

Входные данные
В первой строке входных данных содержится одно целое число \(t\) — число тестовых наборов (\(1 \le t \le 30\)).

Затем следуют \(t\) тестовых наборов. Каждый тестовый набор описывается следующим образом:

В первой строке тестового набора содержатся три целых числа \(n\), \(m\) и \(k\) — число дней, в которые проходят торги, число компаний на рынке и число событий, соответственно (\(1 \le n, m \le 100\), \(1 \le k \le 1000\)).

В следующих \(m\) строках записаны названия компаний и \(n\) чисел — стоимости акций компании в рублях в каждый из дней торгов. Названия компаний состоят из не более чем \(10\) строчных букв латинского алфавита и попарно различны. Стоимости акций — целые числа в диапазоне от \(1\) до \(10^5\) включительно.

В следующих \(k\) строках заданы события покупки/продажи в хронологическом порядке. Событие покупки задается в формате <день> buy <число акций> <название компании>, а событие продажи задается в формате <день> sell <название компании>. При этом <день> — целое число от \(1\) до \(n\), а <число акций> — целое число от \(1\) до \(1000\). Гарантируется, что все события следуют в порядке неубывания дней и корректны, а именно нет продаж некупленных акций и покупок акций, которых нет на рынке.

Выходные данные
Для каждого тестового набора выведите в отдельной строке максимальную прибыль среди всех моментов времени, с относительной или абсолютной погрешностью не более \(10^{-4}\).


Примечание

В первом тестовом наборе изначально до продаж суммарная прибыль равна \(0\), после первой продаже суммарная прибыль становится \(2375\) (случай разобран в примере).

Во втором тестовом наборе промежуточные прибыли равны \(0\), \(-11.11\) (акция продана дороже, но комиссия больше разницы) и \(1948.89\).

В третьем тестовом наборе промежуточные прибыли равны \(0\) и \(-2080\).

В четвертом тестовом наборе промежуточные прибыли равны \(0\) и \(979.9\), деньги потраченные на непроданные акции не учитываются.

Задача на реализациюЗадачи на моделирование
✓ 2✗ 2900средняяВойти и решать
Трансформация массива - 2#49774

Вам дано \(t\) пар массивов \(a_i\) и \(b_i\) равной длины.

За одну операцию модификации можно:

  • Поменять местами любые два элемента массива \(a_i\), но каждый элемент массива может участвовать не более чем в одном обмене.

  • Прибавить к любому элементу массива \(a_i\) единицу. Данную операцию можно применять неограниченное число раз к любому элементу массива.

Для каждой пары массивов найдите минимальное число операций, которые необходимо применить к массиву \(a_i\), чтобы получить массив \(b_i\), или определите, что это невозможно.

Входные данные
В первой строке дано число \(t\) — число пар массивов (\(1 \le t \le 40\)).

В следующих \(3t\) строках содержатся описания пар массивов. Каждая пара описывается тремя строками.

В первой из них дано число \(n_i\) — количество элементов в каждом массиве \(i\)-й пары(\(1 \le n_i \le 10\)). Во второй строке заданы \(n_i\) чисел \(a_{i,j}\) — элементы массива \(a_i\) (\(1 \le a_{i,j} \le 1000\)). В третьей строке заданы \(n_i\) чисел \(b_{i,j}\) — элементы массива \(b_i\) (\(1 \le b_{i,j} \le 1000\)).

Гарантируется, что сумма \(n_i\) по всем тестовым наборам не превосходит \(150\).

Выходные данные
Для каждого пары массивов выведите одно число — минимальное число операций, которые необходимо применить к массиву \(a_i\), чтобы получить массив \(b_i\), или \(-1\), если для данной пары это невозможно.

 
Жадный алгоритмЗадача на реализацию
✓ 1✗ 5—Войти и решать
Чтение книг#49744
У Максима есть n книг различных жанров. В i-й книге ai страниц. Сегодня он хочет прочитать  не менее xj страниц, при этом, чтобы не запутаться в историях, он хочет прочитать как можно меньше книг. 
Помогите Максиму  определить минимальное количество книг, которые он должен прочитать, чтобы общее число прочитанных страниц было не менее xj. Если это невозможно, выведите -1. Максим не может читать одну и ту же книгу дважды. 

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

Первая строка содержит натуральное число n (1 ≤ 𝑛 ≤ 105) - количество книг, которые есть у Максима. Вторая строка  содержит n целых чисел a1, a2, ..., an (1≤ ai ≤104) - количество страниц в i-й книге. Третья строка содержит натуральное число xj (1 ≤ xj ≤ 2⋅109) - количество страниц, которое хочет прочитать Максим.


Формат выходных данных
Выведите ответ на задачу.
Жадный алгоритмИспользование сортировки
✓ 2✗ 16—Войти и решать
Сортировка строк#49712

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

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

В первой строке записаны через пробел размеры матрицы: количество строк N и количество столбцов M ( 1 <= N , M <= 100 ). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами. В последней строке вводится номер столбца K .
 

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

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

Примеры
№ Входные данные Выходные данные
1 
4 5
21 22 23 24 25
26 12 18 29 33
11 37 31 14 39
16 17 18 5 20
1
 
26 12 18 29 33 
21 22 23 24 25 
16 17 18 5 20 
11 37 31 14 39
Алгоритмы сортировкиДвумерные массивы
✓ 49✗ 53700средняяВойти и решать
ЕГЭ-2023-3#49651
Текстовый файл состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита. Определите максимальную длину подстроки, в которой символ Y встречается не более 150 раз.
ЕГЭ_информатикаЕГЭ-24. Обработка символьных строк
1 200труднаяВойти и решать
ЕГЭ-2023-2#49650
Текстовый файл состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита и цифры. Определите максимальную длину подстроки, которая может являться записью числа в шестнадцатеричной системе счисления.
ЕГЭ_информатикаЕГЭ-24. Обработка символьных строк
1 200труднаяВойти и решать
ЕГЭ-2023 - 1#49648
(ЕГЭ-2023) Текстовый файл состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита. Определите минимальную длину подстроки, в которой символ Z встречается не менее 120 раз.
ЕГЭ_информатикаЕГЭ-24. Обработка символьных строк
1 200труднаяВойти и решать
Наибольший отрезок, не содержащий точек#49417
На числовой прямой отмечено N точек с целочисленными координатами. Определите наибольшую длину отрезка, внутри которого нет ни одной точки. 

Формат входных данных
В первой строке записано натуральное число N - количество отмеченных точек (2 <= N <= 103). Во второй строке записано N целых чисел - координаты точек (каждое число по модулю не больше 109).

Формат выходных данных
В первой строке выведите максимальную длину искомого отрезка. Во второй строке выведите координаты его концов (сначала левую координату, затем через пробел правую). Если таких отрезков несколько, то выведите тот отрезок, у которого наименьшая левая координата.
Использование сортировкиКвадратичные сортировки
✓ 46✗ 85300лёгкаяВойти и решать
Ханойская фабрика#49297

Наверняка вы слышали об известной задаче про Ханойские башни, но мало кто знает, что существует целая фабрика, производящая кольца для этой замечательной игры. Однажды на эту фабрику пришел срочный заказ от властителя Египта — Солнцеликого. Солнцеликий требует немедленно прислать ему для игры как можно более высокую башню. Работники фабрики не были готовы к такому необычному заказу, поэтому им придётся собрать какую-то башню из уже произведённых колец.

На складах фабрики находятся \(n\) колец, \(i\)-е кольцо имеет внутренний радиус \(a_i\), внешний радиус \(b_i\) и высоту \(h_i\). Требуется выбрать некоторые из этих колец и упорядочить их таким образом, чтобы выполнялись следующие условия:

  • Внешние радиусы колец образовывали невозрастающую последовательность, то есть кольцо \(j\) можно поставить на кольцо \(i\) только если \(b_j \leq b_i\).

  • Кольца не должны проваливаться друг в друга, то есть кольцо \(j\) можно поставить на кольцо \(i\) только если \(b_j > a_i\).

  • Суммарная высота всех использованных колец должна быть максимальна.

Формат входных данных
В первой строке входных данных записано целое число \(n\) (\(1 \leq n \leqslant 100\,000\)) — количество колец на складах фабрики.

В \(i\)-й из последующих \(n\) строк записаны три числа \(a_i\), \(b_i\) и \(h_i\) (\(1 \leq a_i, b_i, h_i \leq 10^9\), \(b_i > a_i\)) — внутренний радиус, внешний радиус и высота \(i\)-го кольца соответственно.

Формат выходных данных
Выведите максимальную высоту башни, которую смогут получить работники фабрики.


Замечание

В первом примере выгодно поставить друг на друга все имеющиеся кольца в порядке \(3\), \(2\), \(1\).

Во втором примере можно либо поставить кольцо \(3\) на кольцо \(4\) и получить башню высоты \(3\), либо поставить кольцо \(1\) на кольцо \(2\) и получить башню высоты \(4\).

В данной задаче 50 тестов, помимо тестов из условия, каждый из них оценивается в 2 балла. Результаты работы ваших решений на первых 30 тестах будут доступны во время соревнования. Результаты работы на остальных 20 будут доступны после окончания соревнования.

Решение, корректно работающие при \(1 \leq n \leq 9\), наберут не менее \(10\) баллов.

Решение, корректно работающие при \(1 \leq n \leq 15\), наберут не менее \(20\) баллов.

Решение, корректно работающие при \(1 \leq n \leq 1000\), наберут не менее \(60\) баллов.

Жадный алгоритмИспользование сортировкиреализация
✓ 1✗ 3—Войти и решать
Алёна и таблички#49296

На уроке информатики маленькая девочка Алёна осваивает редактирование таблиц в одной очень известной программе.

Сейчас у неё есть таблица из целых чисел, состоящая из \(n\) строк и \(m\) столбцов. Через \(a_{i,j}\) будем обозначать число в \(i\)-й строке и \(j\)-м столбце. Будем говорить, что таблица отсортирована по неубыванию по \(j\)-му столбцу, если \(a_{i, j} \leq a_{i + 1, j}\) для всех \(i\) от \(1\) до \(n - 1\).

Учительница дала Алёне \(k\) заданий. Для каждого из заданий известны два числа \(l\) и \(r\) и требуется ответить на вопрос: если от таблицы оставить только строки с \(l\) по \(r\) включительно, то будет ли она отсортирована по неубыванию хотя бы по одному столбцу? Другими словами, существует ли такое \(j\), что \(a_{i, j} \leq a_{i + 1, j}\) для всех \(i\) от \(l\) до \(r - 1\) включительно.

Алёна ещё слишком маленькая, чтобы справиться с заданием самостоятельно — помогите ей!

Формат входных данных
В первой строке входных данных записаны два целых положительных числа \(n\) и \(m\) (\(1 \leq n \cdot m \leq 100\,000\)) — количество строк и столбцов в таблице соответственно. Обратите внимание, что дано ограничение только на произведение этих чисел, то есть на количество элементов таблицы.

В каждой из следующих \(n\) строк записаны \(m\) целых чисел, \(j\)-e число в \(i\)-й из этих строк соответствует значению \(a_{i, j}\) (\(1 \leq a_{i, j} \leq 10^9\)).

В следующей строке входных данных задано число \(k\) (\(1 \leq k \leq 100\,000\)) — количество заданий учительницы, которые нужно выполнить Алёне.

В \(i\)-й из последующих \(k\) строк числа \(l_i\) и \(r_i\) (\(1 \leq l_i \leq r_i \leq n\)).

Формат выходных данных
В \(i\)-й строке выведите “Yes”, если в таблице, полученной из исходной оставлением строк с \(l_i\) по \(r_i\) включительно будет столбец, по которому она отсортирована по неубыванию, и “No” в противном случае.


Замечание

В приведенном примере таблица не отсортирована ни по одному столбцу, но, например, строки 1–3 отсортированы по столбцу 1, а строки 4–5 по столбцу 3. В данной задаче 100 тестов, помимо тестов из условия, каждый из них оценивается в 1 балл. Результаты работы ваших решений на первых 60 тестах будут доступны во время соревнования. Результаты работы на остальных 40 будут доступны после окончания соревнования.

Решения, корректно работающие при \(1 \leq n, k \leq 100\) и \(m = 1\), наберут не менее 10 баллов.

Решения, корректно работающие при \(1 \leq n, m, k \leq 100\), наберут не менее 40 баллов.

Задачи на моделированиеПрефиксные суммы(минимумы, ...)
✓ 1✗ 13—Войти и решать
Облако хештегов#49295

Вася ведёт публичную страницу организации “Мышь и клавиатура”, где постоянно публикует различные новости из мира спортивного программирования. Для удобства поиска по новостям Вася прикрепляет к каждой из них список хештегов. В данной задаче хештегом называется строка, состоящая из маленьких букв английского алфавита и ровно одного символа ‘#’, расположенного в начале строки. Длиной хештега будем называть количество символов в нём, без учёта символа ‘#’.

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

Поскольку вам не хочется менять порядок хештегов в уже написанной новости, вы решили удалить у некоторых хештегов некоторый суффикс (какое-то количество последних символов), при этом можно даже удалить весь текст хештега, оставив только символ ‘#’, но сам символ ‘#’ удалять нельзя. Из всех возможных вариантов такого удаления вы хотите выбрать тот, в котором суммарно будет удалено минимальное количество символов. Если и таких вариантов несколько, то разрешается использовать любой из них.

Формат входных данных
В первой строке находится одно число \(n\) (\(1 \leq n \leq 500\,000\)) — количество хештегов в новости.

Каждая из следующих \(n\) строк содержит ровно один хештег положительной длины.

Обозначим через \(L\) суммарную длину всех хештегов. Гарантируется, \(L\) не превосходит \(500\,000\).

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

Замечание

Слово \(a_1, a_2, \ldots, a_m\) длины \(m\) лексикографически меньше слова \(b_1, b_2, \ldots, b_k\) длины \(k\), если выполняется одно из двух:

  • либо в первой позиции \(i\), такой что \(a_i \neq b_i\), символ \(a_i\) идёт раньше по алфавиту, чем символ \(b_i\), то есть в первой различающейся позиции символ слова \(a\) меньше символа слова \(b\);

  • либо (если такой позиции нет) \(m < k\), то есть второе слово начинается с первого, но при этом не совпадает с ним.

Про последовательность слов говорят, что они идут в лексикографическом порядке, если каждое слово в нём (кроме последнего) лексикографически не превосходит следующее за ним.

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

Слово, состоящее только из символа ‘#’, лексикографически меньше любого другого хештега. Поэтому в третьем примере мы не можем оставить два первых слова и сократить два вторых.

В данной задаче 50 тестов, помимо тестов из условия, каждый из них оценивается в 2 балла. Результаты работы ваших решений на первых 35 тестах будут доступны во время соревнования. Результаты работы на остальных 15 будут доступны после окончания соревнования.

Решения, корректно работающие при \(1 \leq n, L \leq 15\), наберут не менее \(20\) баллов.

Решения, корректно работающие при \(1 \leq n, L \leq 1\,000\), наберут не менее \(50\) баллов.

Решения, корректно работающие при \(1 \leq n, L \leq 100\,000\), наберут не менее \(70\) баллов.

Задачи на моделированиеСтроки
✓ 2✗ 4—Войти и решать
Игра "Банковские карты"#49294

После четвёртого сезона Шерлок и Мориарти осознали бессмысленность баталии, развернувшейся между ними, и решили дальше соревноваться в мирную игру “Банковские карты”.

Правила у этой игры предельно просты: каждый игрок приносит свою любимую банковскую карту с \(n\)-значным номером. Далее оба игрока по очереди называют последовательные цифры из банковской карты. Если цифры не совпадают, то участник, цифра которого оказывается меньше, получает щелбан от другого игрока. Например, если \(n=3\) и у Шерлока номер карты \(123\), а у Мориарти \(321\), то сначала Шерлок называет число \(1\), а Мориарти называет число \(3\) и Шерлок получает щелбан. Затем и Шерлок и Мориарти называют число \(2\), и щелбан не получает никто. Наконец на третьем шаге, Шерлок называет \(3\), а Мориарти называет \(1\) и получает щелбан.

Шерлок, конечно, будет играть честно, но Мориарти, как настоящий злодей, подсмотрел номер карты Шерлока и теперь хочет называть цифры своей банковской карты не последовательно, а в некотором другом порядке (однако количество каждой из цифр он не изменяет). Например в случае выше, Мориарти мог бы назвать цифры в последовательности \(3\), \(2\), \(1\) и не получил бы щелбанов вообще, а мог назвать \(2\), \(3\) и \(1\) и выдать Шерлоку целых два щелбана.

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

Формат входных данных
В первой строке находится одно целое число \(n\) (\(1 \leqslant n \leqslant 1000\)) — количество цифр в банковских картах Шерлока и Мориарти.

Во второй строке записана последовательность из \(n\) цифр — номер кредитной карточки Шерлока.

В третьей строке записана последовательность из \(n\) цифр — номер кредитной карточки Мориарти.

Формат выходных данных
В первой строке выведите одно число — минимальное число щелбанов, которое обязательно получит Мориарти.

Во второй строке выведите так же одно число — максимальное число щелбанов, которое Мориарти может дать Шерлоку.

Замечание
Первый примерс овпадает с примером разобранным в условии задачи. Во втором примере Мориарти никак не сможет избежать двух щелбанов

В данной задаче 50 тестов, помимо тестов из условия, каждый из них оценивается в 2 балла. Результаты работы ваших решений на первых 30 тестах будут доступны во время соревнования. Результаты работы на остальных 20 будут доступны после окончания соревнования.

Решения, корректно работающие при \(1 \leq n \leq 3\), наберёт не менее \(10\) баллов.

Решения, корректно работающие при \(1 \leq n \leq 8\), наберет не менее \(30\) баллов.

Разные системы счисленияСортировка подсчетом
✓ 6✗ 141 000средняяВойти и решать
Подсчет прибыли#49190
Финансовый аналитик компании "Хлебосушки" анализирует прибыль компании на протяжении N месяцев. Аналитику поставили задачу найти интервал длиной не менее K месяцев с максимальной прибылью. Месяцы имеют сквозную нумерацию, начиная с 1 (с месяца открытия компании). 
Вы - ведущий программист компании. Вам дали задачу написать программу, которая бы находила максимальную прибыль в непрерывном интервале длиной не менее K месяцев. 
 
Формат входных данных
Первая строка содержит натуральное число N (1 < N ≤ 1 000 000) – количество месяцев существования компании и натуральное число K (1 < K < N) – минимально допустимый интервал.  В каждой из следующих N строк находится одно целое число profiti, не превышающее по модулю 10 000 000: прибыль компании за iй месяц. 

Формат выходных данных
Выведите одно число - максимальную прибыль в интервале длиной не менее K месяцев. Гарантируется, что ответ к задаче не превышает 109.
ЕГЭ - вычислительные задачиПрефиксные суммы(минимумы, ...)
✓ 14✗ 63800средняяВойти и решать
Тестирование мессенджера#49029

Перед выпуском VK Messenger’а разработчики из компании IT-компании <<VK>>, как и положено, убеждаются в корректности работы приложения. Проверкой корректности работы систем занимаются тестировщики и QA-инженеры.

Часть функциональных тестов для тестирования смены ников выглядит следующим образом:

  1. генерируется случайный сценарий взаимодействия пользователей с приложением;

  2. в приложении симулируется выполнение этого сценария;

  3. проверяется корректность итогового состояния приложения.

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

Каждый сценарий состоит из трех наборов событий.

  1. Первый набор состоит из событий вида <<в момент времени \(t_i\) поступил запрос регистрации нового пользователя с ID \(\mathtt{id}_i\) и ником \(\mathtt{handle}_i\)>>.

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

  2. Второй набор описывает события вида <<в момент времени \(t_i\) пользователь с ником \(\mathtt{handle}_{i,1}\) отправляет запрос на смену ника на \(\mathtt{handle}_{i,2}\)>>.

    Гарантируется, что для каждого такого запроса ник \(\mathtt{handle}_{i,1}\) кому-то принадлежит. Если \(\mathtt{handle}_{i,2}\) уже занят каким-либо пользователем, запрос отклоняется, иначе пользователь успешно меняет ник. При успешной смене ника старый ник перестает ассоциироваться с каким-либо пользователем, пока кто-то снова его не займет.

  3. Третий набор описывает события вида <<в момент времени \(t_i\) пользователь с ником \(\mathtt{handle}_{i,1}\) отправляет сообщение пользователю с ником \(\mathtt{handle}_{i,2}\).

    Гарантируется, что и \(\mathtt{handle}_{i,1}\) и \(\mathtt{handle}_{i,2}\) на момент времени \(t_i\) соответствуют каким-то зарегистрированным пользователям.

Также гарантируется, что никакие два события не происоходят в одно и то же время, то есть все \(t_i\) уникальны.

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

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

В первой строке ввода дано единственное целое число \(T\) — количество сценариев, которое вам необходимо обработать (\(1 \le T \le 100\)).

Далее следуют \(T\) описаний сценариев. Описание каждого сценария начинается с пустой строки, после чего следуют три набора событий. В первой строке описания \(q\)-го набора (\(q\) от \(1\) до \(3\)) дано единственное целое число \(n_q\) — количество событий в наборе, после чего следуют \(n_q\) строк в указанном ниже формате (\(1 \le n_1 + n_2 + n_3 \le 1000\); \(0 \le n_q\)).

  1. События первого набора задаются в формате <<\(t_i\): REG \(\mathtt{id}_i\) \(\mathtt{handle}_i\)>>.

  2. События второго набора задаются в формате <<\(t_i\): CHANGE \(\mathtt{handle}_{i,1}\) \(\mathtt{handle}_{i,2}\)>>.

  3. События третьего набора задаются в формате <<\(t_i\): SEND \(\mathtt{handle}_{i,1}\) \(\mathtt{handle}_{i,2}\)>>.

Моменты событий \(t_i\) — целые числа от \(1\) до \(10^9\). Также все \(\mathtt{id}_i\) — целые числа от \(1\) до \(10^9\), а \(\mathtt{handle}_i\) — строки из маленьких латинских букв длины не более \(10\).

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

Формат выходных данных
Для каждого сценария выведите требуемую статистику для каждого пользователя.

В первой строке статистики выведите целое число \(q\) — количество зарегистрированных пользователей. В следующих \(q\) строках выведите статистику для каждого пользователя в порядке возрастания их ID в формате <<<\(\mathtt{id}\)> SENT <\(\mathtt{total}\)> TOP <\(\mathtt{count}_\mathrm{top}\)> TO <\(\mathtt{id}_\mathrm{top}\)>>>, где \(\mathrm{total}\) — суммарное количество отправленных пользователем сообщений, \(\mathtt{id}_\mathrm{top}\) — ID пользователя, получившего от него больше всего сообщений, а \(\mathtt{count}_\mathrm{top}\) — само количество сообщений, отправленных пользователю \(\mathtt{id}_\mathrm{top}\).

Если у некоторого пользователя есть несколько собеседников, получивших от него максимальное число сообщений, выведите в качестве \(\mathtt{id}_\mathrm{top}\) минимальный из их ID. Если пользователь не отправлял сообщения, считайте \(\mathtt{count}_\mathrm{top}\) равным \(0\).

 
реализацияСортировка событийХеш
✓ 1✗ 2—Войти и решать
Парковка - 2#49026

Специально для \(n\) сотрудников ИТМО, пользующихся личными автомобилями, планируется открыть парковку. На парковке должно быть ровно \(n\) парковочных мест, каждому сотруднику должно достаться свое место.

Для экономии мест парковка будет разбита на несколько <<рядов>>. Места в каждом ряду нумеруются от \(1\) (самое дальнее от въезда) до длины ряда (самое ближнее ко въезду), и дальние места недоступны, пока не освободятся все более ближние.

Для каждого сотрудника известно, в какое время он приезжает, и в какое время заканчивает работу. Так как сотрудники ИТМО  — очень трудолюбивые люди, каждый из них приезжает на работу в один день, а уезжает уже в следующий. Для каждого известно время, в которое он приезжает на работу \(t^\mathrm{in}_i\), и время, в которое он уезжает на следующий день \(t^\mathrm{out}_i\). Требуется назначить места сотрудникам так, чтобы никому из них не понадобилось ждать

  • появления доступного парковочного места, когда он приезжает;

  • возможности выехать, когда он заканчивает работу.

Более формально, если сотрудникам \(i\) и \(j\) назначены места \(p_i\) и \(p_j\) в одном ряду, и \(p_i < p_j\), должно выполняться \(t^\mathrm{in}_i \le t^\mathrm{in}_j\) и \(t^\mathrm{out}_i \ge t^\mathrm{out}_j\).

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

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

В первой строке ввода дано единственное целое число \(T\) — количество наборов входных данных (\(1 \le T \le 100\)). Далее следуют описания наборов входных данных.

В первой строке описания набора входных данных дано единственное целое число \(n\) — количество сотрудников, которых необходимо разместить на парковке.

Гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(10^5\).

В следующих \(n\) строках перечислены времена въезда и выезда для каждого сотрудника, в \(i\)-й строке через пробел \(t^\mathrm{in}_i\) и \(t^\mathrm{out}_i\) (\(1 \le t^\mathrm{in}_i, t^\mathrm{out}_i \le 10^9\)).

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

В первой строке выведите число \(k\) — минимальное необходимое количество рядов.

В \(i\)-й из следующих \(n\) строк выведите через пробел сначала номер ряда, а затем номер места в этом ряду, которое надо отдать \(i\)-му сотруднику. Ряды и места нумеруются с единицы.

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

 
Жадный алгоритмИспользование сортировки
✓ 2✗ 0—Войти и решать
Парковка#49011

Специально для \(n\) сотрудников ИТМО, пользующихся личными автомобилями, планируется открыть парковку. На парковке должно быть ровно \(n\) парковочных мест, каждому сотруднику должно достаться свое место.

Для экономии мест парковка будет разбита на несколько <<рядов>>. Места в каждом ряду нумеруются от \(1\) (самое дальнее от въезда) до длины ряда (самое ближнее ко въезду), и дальние места недоступны, пока не освободятся все более ближние.

Для каждого сотрудника известно, в какое время он приезжает, и в какое время заканчивает работу. Так как сотрудники ИТМО  — очень трудолюбивые люди, каждый из них приезжает на работу в один день, а уезжает уже в следующий. Для каждого известно время, в которое он приезжает на работу \(t^\mathrm{in}_i\), и время, в которое он уезжает на следующий день \(t^\mathrm{out}_i\). Требуется назначить места сотрудникам так, чтобы никому из них не понадобилось ждать

  • появления доступного парковочного места, когда он приезжает;

  • возможности выехать, когда он заканчивает работу.

Более формально, если сотрудникам \(i\) и \(j\) назначены места \(p_i\) и \(p_j\) в одном ряду, и \(p_i < p_j\), должно выполняться \(t^\mathrm{in}_i < t^\mathrm{in}_j\) и \(t^\mathrm{out}_i > t^\mathrm{out}_j\).

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

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

В первой строке ввода дано единственное целое число \(T\) — количество наборов входных данных (\(1 \le T \le 100\)). Далее следуют описания наборов входных данных.

В первой строке описания набора входных данных дано единственное целое число \(n\) — количество сотрудников, которых необходимо разместить на парковке.

Гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(10^5\).

Во второй строке набора входных данных через пробел перечислены \(n\) целых чисел \(t^\mathrm{in}_i\) — времена приезда сотрудников на работу (\(1 \le t^\mathrm{in}_i \le 10^9\)). В третьей строке в том же формате перечислены \(n\) целых чисел \(t^\mathrm{out}_i\) — времена отъезда сотрудников (\(1 \le t^\mathrm{out}_i \le 10^9\)).

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

В первой строке ответа выведите единственное целое число \(k\) — минимальное необходимое количество рядов. В \(i\)-й из следующих \(k\) строк выведите описание \(i\)-го ряда: первое число в строке \(\mathrm{cnt}_i\) должно быть равно количеству мест в ряду, после чего должны следовать \(\mathrm{cnt}_i\) целых чисел от \(1\) до \(n\) — номера сотрудников, занимающих места этого ряда, в порядке от самого глубокого к самому ближнему ко въезду.

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

 
Использование сортировкиСортировка событий
✓ 4✗ 121 100средняяВойти и решать
Обходы бинарного дерева#48974

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

У бинарного дерева есть три основных обхода: прямой (pre-order), центрированный (in-order) и обратный (post-order).

Прямой обход дерева — это порядок его вершин, полученный следующим рекурсивным алгоритмом:

  1. Добавить корень дерева в обход.

  2. Если у корня есть левый ребёнок, выписать прямой обход его поддерева.

  3. Если у корня есть правый ребёнок, выписать прямой обход его поддерева.

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

Обобщим эти три варианта обхода: пусть в каждой вершине записано целое число \(x\) от \(-1\) до \(1\), обозначающее, в какой момент мы выписываем эту вершину, а именно:

  • \(x = -1\): до обходов поддеревьев её детей;

  • \(x = 0\): между обходами поддеревьев её детей;

  • \(x = 1\): после обходов поддеревьев её детей.

Таким образом, если во всех вершинах записано \(-1\), обход является прямым, если \(0\) — центрированным, если \(1\) — обратным.

Рассмотрим дерево с \(n\) вершинами, пронумерованных от \(1\) до \(n\). Корень дерева — вершина \(1\). Изначально во всех вершинах записано число \(-1\).

В рамках исследования необходимо обработать \(q\) запросов одного из следующих типов:

  1. Поменять числа в вершинах \(l, l+1, \dots, r\) на \(x\) (\(x\) равен \(-1\), \(0\) или \(1\)).

  2. Сообщить, на какой позиции в текущем обходе будет стоять вершина \(i\).

Необходимо вывести ответы на все запросы второго типа.

В первой строке входных данных даны два целых числа \(n\) и \(q\) (\(1 \le n, q \le 100\,000\)).

В следующих \(n\) строках даны по два целых числа \(L_i\) и \(R_i\) (\(0 \le L_i, R_i \le n\)) — номер левого и правого ребёнка вершины \(i\) соответственно, либо \(0\), если соответствующий ребёнок отсутствует.

Гарантируется, что \(L_i\) и \(R_i\) задают корректное бинарное дерево.

Формат входных данных
В следующих \(q\) строках даны запросы. Первое число в строке \(t\) (\(t \in \{1, 2\}\)) — тип запроса.

В случае запроса первого типа далее даны целые числа \(l\), \(r\) и \(x\) (\(1 \le l \le r \le n\), \(x\) равен \(-1\), \(0\) или \(1\)) — границы отрезка вершин, в которых меняются числа, и новое значение.

В случае запроса второго типа далее дано число \(i\) (\(1 \le i \le n\)) — номер вершины, позицию которой в обходе необходимо вывести.

Формат выходных данных
На каждый запрос второго типа выведите единственное число от \(1\) до \(n\) — позицию соответствующей вершины в обходе.

Пусть \(q_1\) — количество запросов первого типа.

В примере обход меняется следующим образом:

  • \([1, 3, 5, 2, 4]\)

  • \([5, 2, 3, 4, 1]\)

  • \([5, 3, 2, 4, 1]\)

Дерево отрезков, RSQ, RMQДеревья
✓ 1✗ 31 100средняяВойти и решать
Игра с таблицей#48967

Дана таблица \(A\) из \(h\) строк и \(w\) столбцов, в каждой ячейке которой записано целое число. Строки пронумерованы от \(1\) до \(h\) сверху вниз, столбцы пронумерованы от \(1\) до \(w\) слева направо.

Разрешается применять к этой таблице следующие операции:

  • выбрать столбец таблицы и удалить его (столбцы слева и справа от него становятся соседними);

  • выбрать строку таблицы и удалить ее (строки сверху и снизу от нее становятся соседними).

Эти операции разрешается применить произвольное число раз в любом порядке.

Определите, возможно ли при помощи этих операций получить из исходной таблицу с суммой чисел, равной заданному числу \(s\), и если да, то какие операции и в каком порядке необходимо применить.

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

Первая строка ввода содержит числа \(h\) и \(w\) — размеры таблицы (\(1 \leq h, w \leq 15\)).

Каждая из следующих \(h\) строк содержит по \(w\) целых чисел — таблицу \(A\) (\(0 \leq A_{i,j} \leq 10^{9}\)).

В последней строке ввода находится число \(s\) — необходимая сумма (\(1 \leq s \leq 10^{18}\)).

Формат выходных данных
Если получить таблицу с суммой чисел \(s\) из исходной невозможно, выведите строку <<NO>>.

Иначе:

  • В первой строке выведите строку <<YES>>.

  • Во второй строке выведите единственное число \(k\) — количество операций с таблицей, которые необходимо применить, чтобы получить из неё таблицу с суммой чисел \(s\).

  • В каждой из следующих \(k\) строк выведите по два целых числа \(t_{j}, i_{j}\), где \(t_{j} = 1\), если очередная операция производится со строкой, и \(t_{j}=2\), если она производится со столбцом таблицы. Число \(i_{j}\) должно быть равно номеру строки или столбца, соответственно, в исходной нумерации, с которой эта операция производится.

В первом примере изначально дана следующая таблица:

\(\begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 2 & 3 & 1 \\ \hline 3 & 1 & 2 \\ \hline \end{array}\)

Удалив третьи строку и столбец получим таблицу с суммой чисел \(8\):

\(\begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 2 & 3 & 1 \\ \hline 3 & 1 & 2 \\ \hline \end{array} \to \begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 2 & 3 & 1 \\ \hline \end{array} \to \begin{array}{|c|c|} \hline 1 & 2 \\ \hline 2 & 3 \\ \hline \end{array}\)

Во втором примере можно показать, что разрешенными операциями невозможно получить таблицу с суммой чисел \(5\) из исходной.

В третьем примере изначально дана таблица:

\(\begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline 5 & 5 & 3 & 2 & 4 \\ \hline 1 & 2 & 4 & 5 & 2 \\ \hline \end{array}\)

Удалив последние две строки и первый столбец, получим таблицу с суммой чисел \(34\):

\(\begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline 5 & 5 & 3 & 2 & 4 \\ \hline 1 & 2 & 4 & 5 & 2 \\ \hline \end{array} \to \begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline 5 & 5 & 3 & 2 & 4 \\ \hline \end{array} \to \begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline \end{array} \to \begin{array}{|c|c|c|c|} \hline 2 & 1 & 4 & 5 \\ \hline 5 & 4 & 1 & 2 \\ \hline 2 & 4 & 3 & 1 \\ \hline \end{array}\)

meet in the middleБитовые операции
✓ 3✗ 391 000средняяВойти и решать
Анаграммы#48946
Слово называется анаграммой другого слова, если оно может быть получено перестановкой его букв.
 
Формат входных данных
Даны два слова на отдельных строках. Слова состоят из строчных латинских букв и цифр. Длины слов не превышают 255.
 
Формат выходных данных
Требуется вывести "YES"  – если введенные слова являются анаграммами друг друга, "NO"  – если нет.
Алгоритмы обработкиСтроки
✓ 19✗ 9700средняяВойти и решать
Поделиться
Класснуть