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

Orders#24733

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

Входные данные
В первой строке на вход подается числа n и m - количество приказов, которые отдал Блейз, и количество команд, которые понимают его войска соответственно. (1 <= n, m <= 5000)
В следующей строке на вход подаются m слов - команды, которые понимают войска Блейза.
В следующих n строках на вход подаются слова - приказы, которые отдает Блейз.
Все строки длиной не превышают 100.

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

Выведите n строк: в строке номер i содержится ответ на задачу для приказа Блейза номер i. Строки, являющиеся ответом на этот запрос, выводятся через пробел в одну строку.

Пример
Ввод

5 5
is in if on of
it
in
of
ij
op

Вывод
if in is
if in is on
if of on
if in is
of on

(с) Евгений Григорьев

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

Поезд#24691

Вам дан массив целочисленных чисел размера n.Необходимо реализовать структуру данных,которая могла бы исполнять следующие операции:
1)Прибавлять всем числам на отрезке [l;r] величину d.
2)Получить сумму чисел на отрезке [l;r].
3)Получить минимум из чисел на отрезке [l;r].
INPUT
На ввод приходит число n – размер массива.В следующей строке,через пробел, даны n чисел - a_i.
Далее задается число m - количество запросов.В следующих m строках запросы трех видов:
1)add l r d - прибавление на отрезке [l;r] числа d.
3)rsq l r - запрос суммы на отрезке [l;r].
3)rmq l r - запрос минимума на отрезке [l;r].
OUTPUT
Ответы для запросов второго и третьего типов через пробел.
P.S. 0 < n, m < 100001 a_i < 1000000001.
P.S.S. Гарантируется,что ответ вмещается в 64-битный тип данных.
INPUT
5
1 2 3 4 5
3
rsq 1 5
add 2 3 1
rmq 2 4
OUTPUT
15 3

(с) Никита Максимов, 2017г.

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

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

Украшение ёлки – 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средняяВойти и решать

Assault#23586

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

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

Но Джерард не только согласился отвести свой флот из бухты Амбера, благодаря чему флоту Корвина удалось добраться до Амбера с целым и невредимым флотом, но и предоставил ему журнал с m записями, в котором в i-ой записи указано, что были перестроены сегменты с l_i по r_i, а также сказано, насколько изменилась укрепленность всех сегментов (укрепленность каждого сегмента на отрезке [li; ri] изменяется на одно и тоже значение t_i).

Корвин m раз предлагает выстрелить по сегментам стены с l по r из p кораблей. Известно, что брешь будет пробита, если на отрезке [l; r] есть хотя бы один сегмент с укрепленностью меньше p. Вы должны ответить ему, будет ли пробита брешь (вывести "YES"), или нет (вывести "NO").

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

На первой строке находятся числа n, m и k (1 <= n, k <= 100000, 1 <= m <= 10000) - количество сегментов, записей и запросов от Корвина соответственно.

На второй строке находятся числа a₁,..., a_n (0 <= a_i <= 10).

В следующих m строках содержатся числа l, r, t (1 <= l <= r <= n, -10 <= t <= 10).

В следующих k строках содержатся числа l, r, p (1 <= l <= r <= n, 1 <= p <= 1000).

Выходные данные
В i-ой строке выведите ответ на i-ый запрос Корвина.

Примеры

№	Входные данные	Выходные данные
1	10 3 3 123 398 287 190 76 15 407 312 323 659 4 9 -99 10 10 -82 4 10 76 9 10 32 5 6 283 4 4 983	NO YES YES

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

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

Siege#23585

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

Блейз и Джулиан строят свои отряды стрелков в линии и дают каждому отряду номер от 1 до n. У каждого отряда есть своя сила, которая выражается некоторым натуральным числом.

Напротив отряда Джулиана с номером i стоит отряд Блейза с номером i. Далее следует m приказов:

Джулиан приказывает отрядам с номерами от l₁ до r₁ дать залп по стоящим напротив них отрядам Блейза.

В то время, пока стрелки Джулиана перезаряжаются, Блейз приказывает отрядам с номерами от l₂ до r₂ дать залп по стоящим напротив стрелкам Джулиана.

После этого все повторяется: Джулиан дает залп, Блейз дает залп и т.д.

Сила залпа и защита вычисляются как сумма сил солдат на отрезке [l; r]. Если сила залпа оказывается выше защиты, то все защищающиеся отряды уничтожаются и больше не могут стрелять (их сила больше не учитывается при подсчете защиты и силы залпа).

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

Если победил Блейз, то выведите "Bleys" (без кавычек).

Иначе выведите "Julian" (без кавычек). Также выведите разницу между силой залпа победившей армии и защитой проигравшей.

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

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

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

В третьей строке находятся n чисел b₁, b₂, ..., b_n (1 <= bi <= 1000) - сила отрядов Блейза.

В следующих m строках находятся числа l и r (1 <= l <= r <= n) - отданные приказы.

Выходные данные
Выведите "Bleys", если победил Блейз. Иначе выведите "Julian". Также выведите число - разницу между силой залпа и защитой.

Примеры

№	Входные данные	Выходные данные
1	10 3 2 2 4 9 1 8 6 1 8 8 1 1 8 9 3 6 5 1 8 6 5 9 1 6 9 10	Julian 30

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

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

Дерево отрезков#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средняяВойти и решать

Урок физкультуры#21998

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

Всего на урок пришло N детей, изначально построившихся таким образом, что рост стоящего на позиции i равен hi (используется нумерация c 1). Можно считать, что все числа hi различны и лежат в диапазоне от 1 до N. Шеренга считается упорядоченной, если на первой позиции стоит школьник ростом один, на второй позиции стоит школьник ростом два и так далее.

Феоктист Всеволодович получает большое удовольствие от процесса упорядочивания школьни- ков, поэтому он всегда выбирает наиболее длинную последовательность обменов. С другой стороны, он не хочет чтобы ученики догадались о том, что он умышленно затягивает построение, поэтому никогда не делает заведомо бессмысленных обменов. А именно, преподаватель никогда не меняет местами школьников на позициях i и j, если hi < h_j . Очевидно, что данное ограничение делает процесс сортировки шеренги по росту конечным.

Староста Саша очень любит играть в волейбол и прекрасно понимает, что чем дольше препо- даватель будет расставлять всех по местам, тем меньше времени останется для игры. Ученики уже построились некоторым образом, а Феоктист Всеволодович вышел поговорить по телефону, так что Саша может успеть поменять местами ровно двух школьников, необязательно стоящих рядом в ше- ренге. Разумеется, он хочет сделать это таким образом, чтобы преподаватель как можно быстрее закончил упорядочивать шеренгу (Саша давно уже раскусил, как именно действует Феоктист Всево- лодович). С информатикой у старосты всегда были определённые проблемы, поэтому ему требуется ваша помощь.

Формат входных данных
В первой строке ввода содержится единственное число N — количество школьников на уроке (1 <= N <= 1 000 000). Во второй строке записано N различных целых чисел h_i (1 <= h_i <= N). i-е число соответствует росту школьника стоящего на i-й позиции.

Формат выходных данных
Выведите два числа — номера позиций школьников, которым необходимо поменяться местами, чтобы минимизировать количество действий преподавателя. Если таких пар несколько, то выведите любую из них. Если никому меняться местами не нужно, выведите -1 -1.

Ввод	Вывод
5 2 4 3 5 1	2 5
4 1 2 3 4	-1 -1
10 2 3 7 1 5 10 4 6 9 8	3 7

Дерево отрезков, RSQ, RMQ Сканирующая прямая Словари Структуры данных

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

What's this#18539

What’s this

После посадки на Марс учёные нашли странную систему пещер, соединённых туннелями. И учёные начали исследовать эту систему, используя управляемых роботов. Было обнаружено, что существует ровно один путь между каждой парой пещер. Но потом учёные обнаружили специфическую проблему. Иногда в пещерах происходят небольшие взрывы. Они вызывают выброс радиоактивных изотопов и увеличивают уровень радиации в пещере. К сожалению, роботы плохо выдерживают радиацию. Но для исследования они должны переместиться из одной пещеры в другую. Учёные поместили в каждую пещеру сенсор для мониторинга уровня радиации. Теперь они каждый раз при движении робота хотят знать максимальный уровень радиации, с которым придётся столкнуться роботу во время его перемещения. Как вы уже догадались, программу, которая это делает, будете писать вы.

Формат входных данных
Первая строка содержит одно целое число N (1≤ N ≤ 100000) — количество пещер. Следующие N −1 строк описывают туннели. Каждая из этих строк содержит два целых числа — a_iи b_i(1 ≤ a_i,b_i≤ N), описывыющие туннель из пещеры с номером a_iв пещеру с номером b_i. Следующая строка содержит целое число Q (1 ≤ Q ≤ 100000), означающее количество запросов. Далее идут Q запросов, по одному на строку. Каждый запрос имеет вид «C U V », где C — символ «I» либо «G», означающие тип запроса (кавычки только для ясности). В случае запроса «I» уровень радиации в U-й пещере (1 ≤ U ≤ N) увеличивается на V (0 ≤ V ≤ 10000). В случае запроса «G» ваша программа должна вывести максимальный уровень радиации на пути между пещерами с номерами U и V (1≤ U,V ≤ N) после всех
увеличений радиации (запросов «I»), указанных ранее. Предполагается, что изначальный уровень радиации равен 0 во всех пещерах, и он никогда не уменьшается со временем (потому что период полураспада изотопов много больше времени наблюдения).
Формат выходных данных
Для каждого запроса «G» выведите одну строкусодержащую максимальный уровень радиации

графы Дерево отрезков, RSQ, RMQ Деревья

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