Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

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

Цепочка слов

Обход в глубину Бор

Цепочкой слов длины n назовем последовательность слов w1, w2, ..., wn такую, что для 1 ≤ i ≤ n слово wi является собственным префиксом слова wi + 1.
 
Напомним, что слово u длины k называется собственным префиксом слова v длины l, если l > k и первые k букв слова v совпадают со словом u.
 
Задано множество слов S = {s1, s2, ..., sm}. Найдите максимальную длину цепочки слов, которую можно построить, используя (возможно, не все) слова этого множества.
 
Входные данные
Первая строка входного файла содержит целое число m(1 ≤ m ≤ 255). Каждая из последующих m строк содержит по одному слову из множества S.
 
Все слова не пусты, имеют длину, не превосходящую 255 символов, и состоят только из строчных букв латинского алфавита.
 
Выходные данные
В выходной файл выведите ответ на задачу.
 
Ввод Вывод
3
a
ab
abc
3
5
a
ab
bc
bcd
add
2

Type Printer

Бор Обход в глубину

Вам нужно напечатать N слов на Movable Type Printer. Movable Type Printers — это старые принтеры, для работы которых требуется ставить маленькие металлические кусочки (каждый из кусочков содержит одну букву) в определенном порядке, образуя таким образом слова. Потом все они вдавливаются в лист бумаги. Таким образом печатается одно слово. Ваш принтер позволяет делать следующие операции:
  • Добавить букву в конец слова, находящегося сейчас на принтере.
  • Удалить последнюю букву из слова, находящегося сейчас на принтере. Эту операцию можно делать, только если слово содержит хотя бы одну букву.
  • Напечатать слово, находящееся на принтере.
Изначально на принтере содержится пустое слово. В конце печати на принтере можно оставить непустое слово. Слова, которые вам даны, вы можете печатать в произвольном порядке.
 
Каждая из трёх операций занимает одну единицу времени. Вам нужно найти последовательность операций, которая печатает данные N слов за минимальное время. Если минимальных последовательностaей несколько, выведите любую.
 
Входные данные
Ваша программа должна считать следующие входные данные:
 
На первой строке число N (1<=N<=25000).
На следующих N строках слова, состоящие из маленьких букв латинского алфавита. Длина каждого слова не превышает 20. Все слова различны.
 
Выходные данные
Ваша программа должна вывести следующие данные:
 
На первой строке M — число операций.
На следующих M строках по одному символу — описание операций. Каждая операция описывается одним символом:
Добавление символа обозначается собственно символом.
Удаление символа обозначается символом «-» (минус, ASCII-код 45).
Операция «напечатать текущее слово» обозначается символом «P» (заглавная латинская буква P).
 
Ввод Вывод
3
print
the
poem
20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P

Abracadabra

Бор

Строка s называется супрефиксом для строки t, если t начинается с s и заканчивается на s. Например, «abra» является супрефиксом для строки «abracadabra». В частности, сама строка t является своим супрефиксом. Супрефиксы играют важную роль в различных алгоритмах на строках.
 
В этой задаче требуется решить обратную задачу о поиске супрефикса, которая заключается в следующем. Задан словарь, содержащий n слов t1, t2, …, tn и набор из m строк-образцов s1, s2, …, sm. Необходимо для каждой строки-образца из заданного набора найти количество слов в словаре, для которых эта строка-образец является супрефиксом.
 
Требуется написать программу, которая по заданному числу n, n словам словаря t1, t2, …, tn, заданному числу m и m строкам-образцам s1, s2, …, sm вычислит для каждой строки-образца количество слов из словаря, для которых эта строка-образец является супрефиксом.
 
Входные данные
Первая строка входного файла содержит целое число n (1 ≤ n ≤ 200 000).
 
Последующие n строк содержат слова t1, t2, …, tn, по одному слову в каждой строке. Каждое слово состоит из строчных букв латинского алфавита. Длина каждого слова не превышает 50. Суммарная длина всех слов не превышает 106. Словарь не содержит пустых слов.
 
Затем следует строка, содержащая целое число m (1 ≤ m ≤ 200 000).
 
Последующие m строк содержат строки-образцы s1, s2, …, sm, по одной на каждой строке. Каждая строка-образец состоит из строчных букв латинского алфавита: Длина каждой строки-образца не превышает 50. Суммарная длина всех строк-образцов не превышает 106. Никакая строка-образец не является пустой строкой.
 
Выходные данные
Выходной файл должен содержать m чисел, по одному на строке.
 
Для каждой строки-образца в порядке, в котором они заданы во входном файле, следует вывести количество слов словаря, для которых она является супрефиксом.

Ввод Вывод
4
abacaba
abracadabra
aa
abra
3
a
abra
abac
4
2
0

Странный сон Константина

Хеш Бор Деревья Деревья

Однажды Константин, поучаствовав в очередной, уже 13-ой по счету международной олимпиаде, возвращался на поезде домой. Он как всегда сидел и размышлял о смысле жизни, попутно решая задачи по программированию. Через некоторое время Константин задремал, но вот беда, для того, чтобы проснуться, он должен решить всплывшую у него в голове задачу, не дающую ему покоя!

В этот раз Константину приснилось дерево, изначально состоящее всего из одной вершины с номером 1. В поставленной им задаче к дереву постепенно добавлялись новые вершины. В i-ую секунду в дерево добавлялась вершина с номером i+1, которая подвешивалась в качестве сына к вершине pi, а на ребре между вершинами i+1 и pi записывалась буква ci.

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

В своем сне Константин вовсе не гений, поэтому решить эту задачу сам он не в силах. Помогите Константину решить задачу и тем самым проснуться.

Входные данные:
В первой строке записано число n - количество запросов на добавление новой вершины в дерево (1 <= n <= 300000).
В следующих n строках описаны запросы добавления вершин. i-ый запрос описывается параметрами pi (1 <= pi <= i) и ci, которые означают, что добавленная вершина с номером i+1 подвешивается к вершине с номером pi в качестве потомка, а на полученном ребре записывается символ ci - строчная буква латинского алфавита.

Выходные данные:
Выведите n строк. В i-ой строке выведите ответ на задачу Константина после добавления i+1-ой вершины.

Примеры:
 

Входные данные Выходные данные
2
1 b
2 p
1
2
3
1 o
1 o
2 j
1
1
2

Игра со строками

Бор Обход в глубину Игры и выигрышные стратегии

Дана игра для двоих игроков со строками.

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

По задданому набору строк определите, кто будет победителем, если оба игрока будут играть оптимально.

Входные данные:
Первая строка содержит целое число n (1 ≤ n ≤ 105).
Каждая из n следующих строк содержит непустую строку из заданного набора. Суммарная длина всех строк из набора не превышает 105. Все строки из набора состоят только из строчных латинских букв.

Выходные данные:
Если победит игрок, который ходит первым, то выведите «First», иначе выведите «Second» (кавычки выводить не нужно).

Примеры:
 

Входные данные Выходные данные
3
a
b
c
First
1
ab
Second

Запросы со строками

Бор

Есть набор строк, который изначально пуст. Необходимо обрабатывать три различные операции над этим набором строк:

  • 1 s: Добавить данную строку в набор.
  • 2 k l: Узнать, существуют ли в наборе k строк (не обязательно различных) таких, что они имеют общий суффикс длины l. Этот суффикс не обязан быть наибольшим.
  • 3 i: Удалить строку из набора, которая была добавлена в i-й операции (если она еще не была удалена).
Входные данные:
В первой строке дано одно целое число - количество операций q (1 <= q <= 105), которые необходимо обработать.
Далее в каждой строке дано описание запроса. Сперва это число 1, 2 или 3, обозначающее тип запроса. 
Если это запрос первого типа, то далее дана строка s, суммарная длина которых не превышает 105.
Если это запрос второго типа, то далее дано два целых числа k и l (1 <= k, l <= 105).
Если это запрос третьего типа, то далее дано число i (1 <= i <= номер текущей операции), где i - номер операции первого типа.

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

Пример:
 
Входные данные Выходные данные
9
1 aba
1 accba
2 2 2
2 2 3
1 aaaa
1 ababa
2 3 2
3 1
2 3 2
YES
NO
YES
NO

Мультимножество и XORы

Жадный алгоритм Бор

У вас есть q запросов и мультимножество A, изначально содержащее только число 0. Запросы бывают трёх видов:

  • + x — добавить в мультимножество A число x.
  • - x — удалить одно вхождение числа x из мультимножества A. Гарантируется, что хотя бы одно число x в этот момент присутствует в мультимножестве.
  • ? x — вам даётся число x, требуется вычислить максимальное значение побитового исключающего ИЛИ (также известно как XOR) числа x и какого-нибудь числа y из мультимножества A.
Мультимножество — это множество, в котором разрешается несколько одинаковых элементов.

Входные данные:
В первой строке входных данных содержится число q (1 ≤ q ≤ 200000) — количество запросов, которые требуется обработать Василию.

Каждая из последующих q строк входных данных содержит один трёх символов «+», «-» или «?» и число xi (1 ≤ xi ≤ 109). Гарантируется, что во входных данных встречается хотя бы один запрос «?».

Обратите внимание, что число 0 всегда будет присутствовать в мультимножестве.

Выходные данные:
На каждый запрос типа «?» выведите единственное целое число — максимальное значение побитового исключающего ИЛИ для числа xi и какого-либо числа из мультимножества A.

Пример:
 
Входные данные Выходные данные
10
+ 8
+ 9
+ 11
+ 6
+ 1
? 3
- 8
? 3
? 8
? 11
11
10
14
13

Короткий код

Бор Жадный алгоритм Деревья

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

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

Строка a является префиксом строки b, если вы можете удалить несколько (возможно, ни одного) символа с конца строки b и получить a.

Найдите минимальную возможную суммарную длину новых имён.

Входные данные:
В первой строке содержится одно целое число n (1 ≤ n ≤ 105) — число переменных в коде Эвана.

Следующие n строк содержат названия переменных по одному на строку. Каждое название не является пустой строкой и содержит только лишь строчные (маленькие) английские буквы. Суммарная длина всех этих строк не больше 105. Все названия переменных различны.

Выходные данные:
Выведите одно целое число — минимально возможную суммарную длину новых названий переменных.

Примеры:
 

Входные данные Выходные данные
3
codeforces
codehorses
code
6
5
abba
abb
ab
aa
aacada
11
3
telegram
digital
resistance
3

Пояснения:
В первом примере одним из наилучших вариантов будет сокращение имён в порядке их ввода до "cod", "co", "c".
Во втором примере можно укоротить последнее имя до "aac" и первое имя до "a" без изменения других имён переменных.

Лотерея

Динамическое программирование на графах Бор

На одном из телеканалов каждую неделю проводится следующая лотерея. В течение недели участники делают свои ставки. Каждая ставка заключается в назывании какого-либо M-значного числа в системе счисления с основанием K (то есть, по сути, каждый участник называет M цифр, каждая из которых лежит в диапазоне от 0 до K−1). Ведущие нули в числах допускаются.

В некоторый момент прием ставок на текущий розыгрыш завершается, и после этого ведущий в телеэфире называет выигравшее число (это также M-значное число в K-ичной системе счисления). После этого те телезрители, у кого первая цифра их числа совпала с первой цифрой числа, названного ведущим, получают выигрыш в размере A1 рублей. Те, у кого совпали первые две цифры числа — получают A2 рублей (при этом если у игрока совпала вторая цифра, но не совпала первая, он не получает ничего). Аналогично угадавшие первые три цифры получают A3 рублей. И так далее. Угадавшие все число полностью получают Am рублей. При этом если игрок угадал t первых цифр, то он получает At рублей, но не получает призы за угадывание t−1, t−2 и т.д. цифр. Если игрок не угадал первую цифру, он не получает ничего.

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

Входные данные
В первой строке задаются числа N (количество телезрителей, сделавших свои ставки, 1N100000), M (длина чисел 1M10) K (основание системы счисления 2 ≤ K ≤ 10). В следующей строке записаны M чисел A1, A2, ..., AM, задающих выигрыши в случае совпадения только первой, первых двух,... , всех цифр (1 ≤ A1 ≤ A2 ≤ ... ≤ AM ≤ 100000). В каждой из следующих N строк записано по одному M-значному K-ичному числу. Числа идут в порядке неубывания.

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

Примеры
Входные данные Выходные данные
1 10 3 2
1 3 100
000
000
001
010
100
100
100
100
110
111
011
6
2 1 1 10
100
0
1
0

Orders

Обход в глубину Перебор Бор

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

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

Контроль доступа

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

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

Каждый IP-адрес − это 4-байтный номер, который записан байт за байтом в десятичной записи. Байты разделены точками следующим образом: <<byte0.byte1.byte2.byte3>> (кавычки добавлены для ясности). Каждый байт записывается как десятичное число от 0 до 255 (включительно) без ведущих нулей. IP-адреса организованы в IP-сети. IP сети описывается двумя 4-байтовыми числами - сетевым адресом и маской сети. И сетевой адрес и маска сети записаны в той же форме, что и IP-адреса. Для того чтобы понять смысл сетевого адреса и маски сети рассмотрим их двоичное представление. Двоичное представление IP адреса, сетевого адреса и маски сети состоит из 32 бит: 8 бит для byte0 (от старших к младшим), затем по 8 бит для byte1, 8 бит для byte2 и 8 бит для byte3.

IP сеть содержит 2N IP-адресов, где 0≤N≤32. В маске сети первые 32–N бита установлены в единицы, и последние N бит установлены в ноль. Сетевой адрес имеет произвольные 32–N первых бит, а последние N бит установлен в ноль. IP сеть содержит все IP-адреса, первые 32−N бит которых равны 32–N
 первых бит сетевого адреса с произвольными N последними битами. Например, IP сеть с сетевым адресом 194.85.160.176 и сетевая маска 255.255.255.248 содержит 8 IP-адресов, с 194.85.160.176 по 194.85.160.183 (включительно).

IP сети, как правило, обозначается как <<byte0.byte1.byte2.byte3/S>>, где <<byte0.byte1.byte2.byte3>> − сетевой адрес, S − это число бит, установленных в единицу в маске сети. Например, IP сети из предыдущего абзаца обозначается как 194.85.160.176/29. Список контроля доступа содержит упорядоченный список правил. Каждое правило имеет одну из следующих форм:

deny from <IP network> − запрещает доступ к ресурсу для любого IP из заданной сети.

deny from <IP address> − запрещает доступ к ресурсу для указанного IP-адреса.

allow from <IP network> − разрешает доступ к ресурсу для любого IP из заданной сети.

allow from <IP address> − разрешает доступ к ресурсу для указанного IP-адреса.

Когда кто-нибудь обращается к какому-либо ресурсу, первым делом проверяется IP-адрес обращающегося по списку контроля доступа. Правила проверяются в том порядке, в котором они перечислены, и применяется первое выполняющееся правило. Если ни одно из правил не соответствует IP-адресу запрашивающей стороны, то доступ предоставляется.

По известному списку контроля доступа и списку запросов от IP-адресов, необходимо выяснить для каждого из запросов будет ли предоставлен доступ к ресурсу.

Входные данные
Первая строка ввода содержит число N − количество правил в списке контроля доступа (0≤N≤100000). Следующие N строк содержат правила по одному в строке. IP сеть всегда записывается как <<byte0.byte1.byte2.byte3/S>>. Следующая строка содержит число M − количество IP адресов, которые следует проверить (0≤M≤100000). Следующие M строк содержат по одному IP адресу в строке.

Выходные данные
Для каждого из M IP-адресов выведите <<A>>, если доступ будет предоставлен, и <<D>> иначе. Все символы следует выводить слитно, не разделяя пробелами.

Hallowen