VK Cup 2018: разбор задач первого квалификационного тура

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

Логином может быть любая последовательность строчных и заглавных латинских букв, цифр и символов нижнего подчеркивания («_»). Однако, чтобы усложнить жизнь мошенникам и уменьшить число нелепых ситуаций из-за невнимательности пользователей, запрещено регистрировать логин, если он похож на хотя бы один из уже существующих логинов. А именно, два логина s и t считаются похожими, если логин s можно получить из логина t путем некоторого количества последовательных применений следующих операций:

• изменить регистр любой буквы (т. е. заменить строчную букву на заглавную или наоборот);
• заменить букву «O» (заглавная латинская буква) на цифру «0» или наоборот;
• заменить цифру «1» (один) на любую из букв «l» (строчная латинская буква «L»), «I» (заглавная латинская буква «i») или наоборот, или же заменить одну из этих букв на другую.

Например, логины «Codeforces» и «codef0rces», а также «OO0OOO00O0OOO0O00OOO0OO_lol» и «OO0OOO0O00OOO0O00OO0OOO_1oI» считаются похожими, а логины «Codeforces» и «Code_forces» — нет.

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

Примеры
[/three_first][three_second]

Входные данные №1
1_wat
2
2_wat
wat_1
Входные данные №2
000
3
00
ooA
oOo
Входные данные №3
_i_
3
__i_
_1_
I
[/three_second][three_third]

Выходные данные №1
Yes

Выходные данные №2
No

Выходные данные №3
No
[/three_third]

Примечание

В первом примере пользователь может зарегистрировать свой логин, поэтому нужно вывести «Yes».

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

В третьем примере пользователь хочет зарегистрировать логин _i_. Ему не удастся это сделать, так как есть логин _1_ (второй из списка существующих).

Изначально нужно отформатировать зарегистрированные логины. Для каждого из них сделаем следующее:

1. заменим все заглавные буквы на строчные;
2. заменим все буквы o на цифру 0;
3. заменим все буквы i и l на цифру 1.

Если новый логин равен какому-то из отформатированных логинов, то пользователь не сможет зарегистрировать новый логин. В против случае, сможет.

Иногда вспоминаешь старого друга и начинаешь вспоминать все, что с ним связано. Хорошо, что есть социальные сети: они хранят вашу переписку с самого знакомства, и можно с легкостью прочитать, о чем же вы спорили 10 лет назад.

Формально, ваша переписка — упорядоченная по времени последовательность сообщений, пронумерованных от 1 до n, где n — общее количество сообщений в переписке.

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

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

Определите количество различных сообщений, которые вы прочтете, если начинать читать переписку, открыв диалог на сообщении t, для каждого t от 1 до n. Считайте ответ для каждого случая независимо. Если начинать читать с сообщения номер x, то на экране изначально показаны k сообщений до сообщения x, само сообщение x и k сообщений после. Сообщения, прочитанные несколько раз, считаются за одно.

Примеры
[/three_first][three_second]

Входные данные №1
6 0
0 1 1 2 3 2
Входные данные №2
10 1
0 1 0 3 4 5 2 3 7 0
[/three_second][three_third]

Выходные данные №1
1 2 2 3 3 3

Выходные данные №2
2 3 3 4 5 6 6 6 8 2
[/three_third]

Примечание

Если начинать с шестого сообщения в первом примере, то вы прочитаете шестое сообщение, затем второе, затем первое и закончите, т. к. из первого сообщения нет ссылки.

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

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

Если в сообщении y нет ссылки на другое сообщение, то ответ для него — это длина отрезка [y - k, y + k] (при этом нужно не забывать, что левая граница отрезка должна быть положительна, а правая не должна превышать n, то есть левая граница — это max(1, y - k), а правая — это min(n, y + k)).

В противном случае, пусть из сообщения y ссылка ведёт в сообщение z. Так как по условию z < y, то cntz уже посчитано. В таком случае в ответ для y войдут все сообщения, которые насчитаны для z, а также добавятся новые сообщения из отрезка [y - k, y + k], которые не входят в отрезок для сообщения z (так как они уже посчитаны), который равен [z - k, y + k]. Опять же нужно помнить, что для каждого из отрезков левая граница должна быть положительна, а правая не должна превышать n.

После рассмотрения всех сообщений нужно вывести ответный массив cnt.

Поликарп разрабатывает проект на языке Vaja и использует популярную систему управления зависимостями Vamen. С точки зрения Vamen и проекты, и библиотеки на Vaja называются просто проектами.

В Vamen каждый проект имеет уникальное название из строчных латинских букв длины от 1 до 10 и версию — положительное целое число от 1 до 106. Каждый проект (помните, что в этот термин включается не только название, но и конкретная версия) может зависеть от других проектов. Конечно, все зависимости ациклические.

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

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

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

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

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

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

Примеры
[/three_first][three_second]

Входные данные №1
4
a 3
2
b 1
c 1

b 2
0

b 1
1
b 2

c 1
1
b 2
Входные данные №2
3
abc 1
2
abc 3
cba 2

abc 3
0

cba 2
0
[/three_second][three_third]

Выходные данные №1
2
b 1
c 1

Выходные данные №2
1
cba 2
[/three_third]

Примечание

Первый пример изображён на рисунке ниже. Стрелка из проекта A в проект B означает, что проект B напрямую зависит от проекта A. Закрашены проекты, от которых зависит проект Поликарпа «a» с версией 3.

Второй пример изображён на рисунке ниже. Стрелка из проекта A в проект B означает, что проект B напрямую зависит от проекта A. Закрашены проекты, от которых зависит проект Поликарпа «codehorces» с версией 5. Обратите внимание, взят проект «extra 1», а не «extra 3», так как проект «mashadb 1» и все его зависимости отброшены из-за проекта «mashadb 2».

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

Также нам понадобятся два ассоциативных массива: в первом будем хранить по названию проекта минимальное расстояние до него (ассоциативный массив dist), во втором — по названию проекта хранить версию, от которой зависит наш проект (ассоциативный массив version).

После этого реализуем стандартный обход в ширину из нашего проекта. Будем использовать первые два ассоциативных массива для удобства реализации. Пусть мы достали из очереди номер, который соответствует проекту с названием name и версий ver. Тогда, если наш проект еще не зависел от проекта с названием name, либо версия, от которой зависит наш проект не равна ver (для проекта с названием name), то удалим из очереди этот номер и посмотрим на следующий элемент в ней. Описанную проверку можно выполнить

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

После завершения обхода в ширину весь ответ содержится в version.

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

Аркадий набирает слова, знаки препинания и пробельные символы один за другим, для набора каждой буквы и каждого знака (в том числе перевода строки) требуется одно нажатие клавиши на клавиатуре. При этом, когда Аркадий набрал непустой префикс некоторого слова (в том числе слово полностью), его редактор подсказывает возможное автоматическое дополнение для текущего слова: слово из числа тех, которые Аркадий набрал до этого, префикс которого совпадает с текущим набранным префиксом, если такое слово уникально. Например, если Аркадий уже набрал слова «codeforces», «coding» и еще раз «codeforces», то, если он наберет префикс «cod», то редактор ему ничего не подскажет, а если он наберет префикс «code», редактор подскажет «codeforces». При этом не важно, собирается ли Аркадий набрать слово «codeforces» или, например, «codebest».

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

Формально словом называется непрерывная последовательность латинских букв, с обоих концов ограниченная пробелами, знаками препинания, началом или концом строки или текста. Аркадий использует только строчные буквы. Например, в тексте «it’s well-known that tic-tac-toe is a paper-and-pencil game for two players, x and o.» 20 слов.

Примеры
[/three_first][three_second]

Входные данные №1
snow affects sports such as skiing, snowboarding, and snowmachine travel.
snowboarding is a recreational activity and olympic and paralympic sport.
Входные данные №2
‘co-co-co, codeforces?!’
Входные данные №3
thun-thun-thunder, thunder, thunder
thunder, thun-, thunder
thun-thun-thunder, thunder
thunder, feel the thunder
lightning then the thunder
thunder, feel the thunder
lightning then the thunder
thunder, thunder

Выходные данные №1
141

Выходные данные №2
25
Выходные данные №3
183
[/three_third]

Примечание

В первом примере нужно воспользоваться автодополнением для первого слова «snowboarding» после того, как набран префикс «sn», и для второго слова «snowboarding» после того, как набран префикс «snowb». Суммарно это экономит 7 нажатий.

Во втором примере все равно, пользоваться автодополнением, или нет.

В третьем нужно можно воспользоваться автодополнением для второго слова после набора «t», для третьего слова — после набора «t», затем набрать его до конца, далее слова «thun» надо набирать полностью, а для набора «thunder» необходимо набирать «thund», затем пользоваться автодополнением, кроме того, надо пользоваться автодополнением для вторых слов «lightning» и «feel» после набора одной буквы.

Изначально выделим все слова, которые есть в тексте. Количество остальных символов прибавим к ответу. Также нужно не забыть добавить к ответу количество строк во входных данных, так как каждая строка завершается переводом строки (это ещё одно нажатие на клавишу).

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

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

Если же такая вершина есть, то будем действовать следующим образом. Пусть мы посмотрели первые pos букв строки (то есть стоим сейчас в позиции pos, так как работаем в 0-индексации). Пойдем дальше по строке с позиции pos (сохраним значение pos в startPos). Будем увеличивать pos до тех пор, пока количество префиксов, оканчивающихся в соответствующей вершине бора, равно одному.

Пусть endPos — это первая буква в строке, для которой предыдущее условие нарушилось. Тогда, если вершина бора, в которой мы остановились, не является листом, нужно прибавить к ответу длину текущей строки.

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

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