#112793

Партии

Темы: [Standard Template Library] [Алгоритмы на графах]

В стране Байтландии есть n городов, соединенных дорогами. Каждая дорога двухсторонняя и имеет некоторую длину. Также, в стране есть две партии — одна выступает за то, что вилку необходимо держать во время еды в левой руке, другая — за то, что вилку необходимо держать в правой руке. В каждый момент времени каждый из городов поддерживает только одну партию. Вот только время от времени в городах происходят перевороты и в одном из городов поддерживаемая партия меняется на противоположную.

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

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

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

Первая строка входного файла содержит три целых числа n, m и k (1 ≤ n, m, k ≤ 100000) — количество городов, дорог и переворотов соответственно.

Вторая строка содержит строку s длиной n, описывающую политическую ситуацию в стране на момент начала наблюдения. Символ L на i-ой позиции означает, что город номер i поддерживает партию, выступающую за то, что вилку необходимо держать в левой руке, символ R — в правой.

Следующие m строк содержат по три целых числа a_i, b_i и l_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i, 1 ≤ l_i ≤ 10⁹) — номера городов, которые соединены i-ой дорогой и ее длина. Каждая пара городов соединена не более, чем одной дорогой.

В последней строке содержится k чисел --- номера городов c_j (1 ≤ c_j ≤ n), в которых происходили перевороты в порядке их происшествия. Поскольку все города достаточно консервативны, то в каждом городе произошло не более одного переворота, то есть все c_j различны.

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

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

Каждое описание должно быть выведено на отдельной строке и содержать три целых числа d_i, x_i и y_i — минимальное расстояния между городами, поддерживающими одну партию и номера этих городов, соответственно. Если таких пар несколько, выведите любую. Гарантируется, что хотя бы одна такая пара всегда существует.

Подгруппа 1.

n ≤ 100. Решение оценивается в 30 баллов.

Подгруппа 2.

n ≤ 2000, Решение оценивается в 30 баллов.

Подгруппа 3.

Дополнительные ограничения отсутствуют. Решение оценивается в 40 баллов.

Примеры

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

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

#112810

Контрольная работа

Темы: [Условный оператор (if)]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 6-9 классы, 2015, Задача A ]

Петя и Вася — одноклассники и лучшие друзья, поэтому они во всём помогают друг другу. Завтра у них контрольная по математике, и учитель подготовил целых K вариантов заданий.

В классе стоит один ряд парт, за каждой из них (кроме, возможно, последней) на контрольной будут сидеть ровно два ученика. Ученики знают, что варианты будут раздаваться строго по порядку: правый относительно учителя ученик первой парты получит вариант 1, левый — вариант 2, правый ученик второй парты получит вариант 3 (если число вариантов больше двух) и т.д. Так как K может быть меньше чем число учеников N, то после варианта K снова выдаётся вариант 1. На последней парте в случае нечётного числа учеников используется только место 1.

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

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

В первой строке входных данных находится количество учеников в классе 2 ≤ N ≤ 10⁹. Во второй строке — количество подготовленных для контрольной вариантов заданий 2 ≤ K ≤ N. В третьей строке — номер ряда, на который уже сел Петя, в четвёртой — цифра 1, если он сел на правое место, и 2, если на левое.

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

Если Вася никак не сможет писать тот же вариант, что и Петя, то выведите - 1. Если решение существует, то выведите два числа — номер ряда, на который следует сесть Васе, и 1, если ему надо сесть на правое место, или 2, если на левое. Разрешается использовать только первые N мест в порядке раздачи вариантов.

Примеры тестов

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

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

2 2

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

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

-1

Примечание

В первом примере вариантов 2, поэтому наилучшее место для Васи находится сразу за Петей. Во втором примере Петя будет единственным, кто получит вариант 13.

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

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

Подзадача 1. N ≤ 100. Оценивается из 52 баллов.

Подзадача 2. N ≤ 10⁹. Оценивается из 48 баллов.

#112811

Хорошая строка

Темы: [Рекурсия] [Одномерные массивы]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 6-9 классы, 2015, Задача B ]

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

Прямо сейчас юный исследователь полностью поглощён изучением хорошести строк. Хорошестью строки называется количество позиций от 1 до L - 1 (где L — длина строки), таких, что следующая буква в строке является следующей по алфавиту. Например, хорошесть строки "abcdefghijklmnopqrstuvwxyz" равна 25, а строки "abdc" — только 1.

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

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

Первая строка ввода содержит единственное целое число N — количество различных букв в наборе (1 ≤ N ≤ 26). Обратите внимание: в наборе всегда используются N первых букв латинского алфавита.

Следующие N строк содержат целые положительные числа c_i — количество букв соответствующего типа (1 ≤ c_i ≤ 10⁹). Таким образом, первое число означает количество букв "a", второе число задаёт количество букв "b" и так далее.

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

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

Примеры тестов

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

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

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

2
3
4

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

Примечание

В первом тесте имеется по одной дощечке с каждой из 3 различных букв. Ответ 2 достигается на строке "abc"

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

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

Подзадача 1. Во всех тестах данной группы c_i ≤ 100. Данная подзадача оценивается из 40 баллов.

Подзадача 2. Во всех тестах данной группы c_i ≤ 1 000 000. Данная подзадача оценивается из 30 баллов.

Подзадача 3. Во всех тестах данной группы c_i ≤ 10⁹. Данная подзадача оценивается из 30 баллов.

#112812

Шляпа

Темы: [Строки] [Структуры данных]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 6-9 классы, 2015, Задача C ]

Летом Максим съездил в Летнюю Какую-то Школу, где, помимо учёбы, ему очень запомнилась игра «Шляпа», в которую он вместе с друзьями играл всю смену. Опишем правила игры, которых они придерживались. Обратите внимание: эти правила немного отличаются от общепринятых.

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

Теперь Максим провёл турнир для N команд из своей школы и должен определить победителя. Он неаккуратно вёл записи игры и не отмечал, сколько слов отгадала каждая из команд, зато он записывал в хронологическом порядке каждый раз, когда какая-либо команда доставала какую-либо бумажку из шляпы. Всего таких записей M, и они следуют в хронологическом порядке. Помогите Максиму восстановить по сделанным записям, сколько слов отгадала каждая из команд.

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

В первой строке дано количество команд N и количество попыток отгадать слова M (1 ≤ N ≤ 100 000, 1 ≤ M ≤ 100 000). В следующих M строках сначала указывается номер n_i команды, пытавшейся отгадать слово, а через пробел дано слово w_i, написанное на бумажке. Номера команд лежат в диапазоне от 1 до N. Все слова w_i состоят из строчных латинских букв и имеют ненулевую длину, не превосходящую 10 букв.

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

Выведите в одну строку N чисел, i-ое число должно равняться количеству слов, отгаданному i-ой командой.

Примеры тестов

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

2 3
1 hat
1 shirt
2 hat

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

1 1

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

3 2
1 mom
3 dad

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

1 0 1

Примечание

В первом примере первая команда отгадала слово shirt, а вторая слово hat.

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

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

Подзадача 1. 1 ≤ N ≤ 2000, 1 ≤ M ≤ 2000. Каждое слово встречается только один раз. Оценивается из 20 баллов.

Подзадача 2. 1 ≤ N ≤ 2000, 1 ≤ M ≤ 2000. Оценивается из 30 баллов.

Подзадача 3. 1 ≤ N ≤ 100 000, 1 ≤ M ≤ 100 000. Оценивается из 50 баллов.

#112817

Вышивка жемчугом

Темы: [Сканирующая прямая] [Алгоритмы на графах]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2015, 1 тур, Задача C ]

Дано изображение дерева из \(n\) вершин на прямоугольной сетке. Каждое ребро — либо вертикальный, либо горизонтальный отрезок длины \(1\) Дано \(q\) запросов, каждый имеет вид "сколько компонент связности образуется при вырезании данного прямоугольного фрагмента"

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

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

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

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

Первая строка входных данных содержит два целых числа a и b — размеры полотенца в клетках по горизонтали и вертикали.

Вторая строка содержит два числа \(n\) и \(q\) — количество жемчужин в узоре и количество фрагментов соответственно.

Следующие (\(n − 1\)) строк содержат описания стежков. Каждый стежок имеет один из следующих видов:

• \(h \times y\) означает, что клетки с координатами \((x, y)\) и \((x + 1, y)\) содержат жемчужины, соединённые горизонтальным стежком (\(1 \le x \le a − 1; 1 \le y \le b\));

• \(v \times y\) означает, что клетки с координатами \((x, y)\) и \((x, y + 1)\) содержат жемчужины, соединённые вертикальным стежком (\(1 \le x \le a; 1 \le y \le b − 1\)).

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

Следующие \(q\) строк описывают фрагменты. Каждое описание содержит четыре целых числа \(x_1\), \(y_1\), \(x_2\) и \(y_2\) — координаты левой нижней и правой верхней клетки фрагмента (\(1 \le x_1 \le x_2 \le a; 1 \le y_1 \le y_2 \le b\)).

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

Выходные данные должны содержать \(q\) строк, где \(i\)-я строка содержит количество связных частей узора в \(i\)-м фрагменте.

Таблица системы оценивания

Замечание

Пояснение к тесту из условия

Примеры

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

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