HASH

Примеры

Волшебные грибы

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

Таким образом, если обозначить количество грибов, посаженных на грядке, созданной в день номер i, как c_i, то оно будет считаться по формуле c_i = c_i - 1 + c_i - 2. Так, в первый и второй дни было посажено по одному грибу, в третий — два, в четвертый — три, в пятый — пять и так далее.

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

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

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

Первая строка входного файла содержит одно число N (1 ≤ N ≤ 1000000) — количество исследуемых грядок. Следующие n строк содержат по одному целому числу a_i — количества грибов на исследуемых грядках. Размер входного файла не превышает 1 Мб.

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

Для каждого числа, данного во входном файле, выведите «Yes», если грядка с таким количеством грибов является волшебной, и «No» — если не является. Ответы разделяйте переводами строк.

Примеры

Путешествие по строке

Скажем, что последовательность строк t₁ , ..., t_k является путешествием длины k , если для всех i > 1 t_i является подстрокой t_{i - 1} строго меньшей длины. Например, { ab , b } является путешествием, а { ab , c } или { a , a } — нет.

Определим путешествие по строке s как путешествие t₁ , ..., t_k , все строки которого могут быть вложены в s так, чтобы существовали (возможно, пустые) строки u₁ , ..., u_{k + 1} , такие, что s = u₁t₁u₂ t₂ ... u_k t_k u_{k + 1} . К примеру, { ab , b } является путешествием по строке для abb , но не для bab , так как соответствующие подстроки расположены справа налево.

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

Входные данные
В первой строке задано целое число n ( 1 ≤ n ≤ 500 000 ) — длина строки s .

Во второй строке содержится строка s , состоящая из n строчных английских букв.

Выходные данные
Выведите одно число — наибольшую длину путешествия по строке s .

Примечание
В первом примере путешествием по строке наибольшей длины является { abcd , bc , c } .

Во втором примере подходящим вариантом будет { bb , b } .

Примеры

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

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

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

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

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

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

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

Примеры:
 

Том Сойер и слово на заборе

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

Входные данные:
В первой строке дано слово s (1 <= |s| <= 200000), состоящее из строчных латинских букв.

Выходные данные:
Выведите минимально возможное по длине слово g, которое нужно дописать, чтобы слово sg на заборе стало палиндромом. Если дописывать ничего не надо, то выведите '-'.

Примеры:
 

Гекльберри Финн и две строки

У Гекльберри Финна есть две строки s и t одинаковой длины n.
Гекльберри Финну нравится, когда у строк одинаковые префиксы (начала), поэтому он может поменять местами два символа в строке s, чтобы общий префикс строк s и t стал больше.
Однако этот трюк довольно утомительный, поэтому Гекльберри Финн либо совсем не будет его делать, либо сделает ровно один раз.

Помогите Гекльберри Финну определить наибольшую длину общего префикса строк s и t, которую он может получить.


Входные данные:
В первой строке дано натуральное число n (1 <= n <= 200000) - длина строк s и t
Во второй строке дана строка s, состоящая из строчных латинских букв.
В третьей строке дана строка t, состоящая из строчных латинских букв.

Выходные данные:
Выведите одно натуральное число - наибольшую длину общего префикса s и t, которую можно получить, применив операцию обмена двух символов в строке s не более одного раза.

Примеры:
 

Бункеры

Петя и Вася с упоением играют в шпионов. Сегодня они планируют, где будут 
расположены их секретные бункеры и штаб-квартира. 

Пока Петя и Вася решили, что им понадобится ровно n бункеров, которые для секретности будут пронумерованы числами от 1 до n. 
Некоторые из них будут соединены двусторонними тоннелями, причем для надежности и секретности по тоннелям можно будет попасть из любого бункера в любой единственным образом.
Петя и Вася даже решили, какие из бункеров будут соединены тоннелями, но выбрать, какой из них будет штаб-квартирой, они не могут. 
Мальчики хотят выбрать ее и разделить оставшиеся бункеры между собой таким образом, чтобы им досталось поровну бункеров к штаб-квартире вело бы ровно два тоннеля: один от бункера, принадлежащего Васе, другой - от бункера, принадлежащего Пете. 
                                                                                   
Уставший Петя пошел к себе домой, а утром Вася показал ему план, на котором бункеры были обозначены точками, а тоннели отрезками. 
Кроме того, Вася выбрал штаб-квартиру таким образом, что нарисованный им план был симметричен относительно прямой, проходящей через точку, которая соответствовала штаб-квартире.
 
Хотя Петя почти сразу показал Васе, что тот ошибся и не нарисовал половину бункеров, ему стало интересно, можно ли выбрать штаб-квартиру и нарисовать такой симметричный план.

Входные данные:
В первой строке входного файла находится одно целое число n (1 <= n <= 10⁵) - количество бункеров. 
В следующих n - 1 строках находится по два целых числа u_i и v_i (1 <= u_i, v_i <= n, u_i ≠ v_i) - номера бункеров, которые соединяет i-ый тоннель. 
Гарантируется, что между любыми двумя бункерами существует единственный путь.

Выходные данные:
В выходной файл выведите "YES", если можно выбрать штаб-квартиру и нарисовать такой план, или "NO" если это невозможно.

Примеры:
 

Censoring

Цепочка слов

Будем называть цепочкой слов длины n последовательность слов w₁, w₂, …, w_n, такую, что для всех i от 1 до n – 1 слово w_i является собственным префиксом слова w_i+1.

Слово u длины k называется собственным префиксом слова v длины l, если l > k и первые k букв слова v совпадают со словом u. Например, «program» является собственным префиксом слова «programmer».

Задано множество слов S = {s₁, s₂, …, s_m} и последовательность чисел x[1], x[2], …, x[k]. Требуется найти такие числа l и r (l ≤ r), что s_x[l], s_x[l + 1], …, s_x[r – 1], s_x[r] является цепочкой слов, и количество слов в цепочке (число r – l + 1) максимально.

Входные данные
Первая строка входного файла содержит целое число m (1 ≤ m ≤ 250 000). Каждая из следующих m строк содержит по одному слову из множества S.

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

Следующая строка содержит число k (1 ≤ k ≤ 250 000). Последняя строка входного файла содержит k чисел — последовательность чисел x[1], x[2], …, x[k] (для всех i выполнено 1 ≤ x[i] ≤ m).

Выходные данные
Выведите в первой строке выходного файла два числа: l и r. Если оптимальных ответов несколько, выведите любой из них. Разделяйте числа пробелом.

Хеширование с удалением

Реализуйте структуру данных типа “множество строк”. Хранимые строки  – непустые последовательности  длиной не более 10 символов, состоящие из строчных латинских букв. Структура данных должна поддерживать операции добавления строки в множество, удаления строки из множества и проверки принадлежности данной строки множеству. Максимальное количество элементов в хранимом множестве не превосходит 10⁶.

Входные данные
Каждая строка входных данных задает одну операцию над множеством. Запись операции состоит из типа операции и следующей за ним через пробел строки, над которой проводится операция. Тип операции  – один из трех символов:    + означает добавление данной строки в множество;     -  означает удаление  строки из множества;      ?  означает проверку принадлежности данной строки множеству. Общее количество операций во входном файле не превосходит 106. Список операций завершается строкой, в которой записан один символ # – признак конца входных данных. При добавлении элемента в множество НЕ ГАРАНТИРУЕТСЯ, что он отсутствует в этом множестве. При удалении элемента из множества НЕ ГАРАНТИРУЕТСЯ, что он присутствует в этом множестве.

Выходные данные
Программа должна вывести для каждой операции типа ? одну из двух строк YES или NO, в зависимости от того, встречается ли данное слово в нашем множестве.

Списал ли Петя?

Учитель математики дал двум ученикам, Пете и Васе, задания. Нужно мог ли Петя списать все заданяи у Васи, то есть является ли множество заданий Пети подмножеством заданий Васи .

Множество A является подмножеством B (A ⊆ B), если каждый элемент A также является элементом B.

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

В первой строке — число N (1 ≤ N ≤ 100000) — количество заданий Пети.

Во второй строке — N целых чисел — номера заданий Пети (1 ≤ номер ≤ 1000000).

В третьей строке — число M (1 ≤ M ≤ 100000) — количество заданий Васи.

В четвёртой строке — M целых чисел — номера заданий Васи.

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

"YES", если множество Пети является подмножеством множества Васи, иначе "NO".

H. Who needs suffix structures?

Массивы-палиндромы

Кай работает в лаборатории изучения массивов, он экспериментирует с двумя массивами натуральных чисел: \(A = [a_1, a_2, \ldots, a_n]\) длины \(n\) и \(B = [b_1, b_2, \ldots, b_m]\) длины \(m\).

Эксперимент, который проводит Кай, устроен следующим образом. У каждого из массивов отбрасывается произвольный, возможно пустой, префикс, а также произвольный, возможно пустой, суффикс, таким образом, чтобы оставшиеся части массивов имели равную длину. Обозначим получившиеся массивы как \(A'\) и \(B'\), а их длину как \(k\). Затем Кай суммирует поэлементно получившиеся массивы, итоговый массив Кай обозначает как \(C = [c_1, c_2, \ldots, c_k]\).

Пусть, например, \(n = 5\), \(A = [4, 3, 3, 2, 1]\), \(m = 6\), \(B = [4, 1, 5, 1, 3, 2]\), от массива \(A\) отбрасывается первый и последний элемент, от массива \(B\) три первых. После этого массивы имеют вид \(A' = [3, 3, 2]\), \(B' = [1, 3, 2]\), результат их поэлементного суммирования \(C = [4, 6, 4]\).

Задача Кая заключается в том, чтобы получать такие \(C\), которые являются массивами-палиндромами, то есть если числа на первой и последней позиции совпадают, числа на второй и предпоследней позиции совпадают, и так далее, для всех \(i\) числа на позициях \(i\) и \(k - i + 1\) совпадают.

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

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

Во второй строке ввода даны \(n\) целых чисел \(a_{i}\) — массив \(A\) (\(1 \leqslant a_i \leqslant 100\)).

В третьей строке ввода даны \(m\) целых чисел \(b_{j}\) — массив \(B\) (\(1 \leqslant b_j \leqslant 100\)).

Формат выходных данных
Выведите единственное целое число — максимальное \(k\), что Кай в результате эксперимента может получить массив-палиндром длины \(k\).

Тестирование мессенджера - 2

Перед выпуском 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. События первого набора задаются в формате <<REG \(\mathtt{id}_i\) BY \(\mathtt{handle}_i\) AT \(t_i\)>>.

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

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

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

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

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

В первой строке статистики выведите целое число \(q\) — количество зарегистрированных пользователей. В следующих \(q\) строках выведите статистику для каждого пользователя в порядке возрастания их ID в формате <<<\(\mathtt{id}\)> RECEIVED <\(\mathtt{total}\)> TOP <\(\mathtt{count}_\mathrm{top}\)> FROM <\(\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\).

K-mex

Вы думали, что сможете спокойно выехать из Озёрска, погостив у друга? Конечно же, нет. Полицейский опять остановил вас и снова просит решить задачу, чтобы удостовериться, что вы можете выехать из города. Придётся вам решить очередную задачу.
Изначально у вас множество, в котором есть единственный элемент — это 0. Вам нужно будет поддерживать q запросов следующего вида:
•    + x — добавить число x в множество. Гарантируется, что раньше его там не было,
•    - x — удалить число x из множества. Гарантируется, что это число там есть,
•    ? k — найти k − mex множества.
В нашей задаче мы считаем, что k − mex множества — это наименьшее целое неотрицательное число x, которое делится на k и которого нет в множестве.
Входные данные
В первой строке находится целое число q (1 <= q <= 2 · 10⁵) — количество запросов.
В следующих q строках находятся описания запросов. Если это запрос добавления, то в формате
+ x (1 <= x <= 10¹⁸), если запрос удаления, то - x (1 <= x <= 10¹⁸), если же запрос поиска, то ? k (1 <= k <= 10¹⁸). Гарантируется, что будет хотя бы один запрос типа ?.

Выходные данные
Для каждого запроса типа ? выведите k − mex множества.
 

Примеры

Свойства объектов - 1

В хранилище Васи находится n объектов, пронумерованных от 1 до n, у каждого из которых есть некоторое количество свойств (возможно, ни одного). Каждое свойство представлено в виде натурального числа от 1 до 10⁹.
Проанализировав устройство своего хранилища, Вася решил, что оно должно поддерживать две операции:
 -  Удаление устаревшего свойства c. При удалении свойства, оно удаляется у всех объектов, которым принадлежит.
Если указанного свойства не существует, ничего делать не нужно.
 -  Найти количество оставшихся свойств у объекта с номером r.
Васе очень нужно реализовать эту функциональность, и он обратился к вам за помощью. Помогите ему - напишите программу, которая будет поддерживать обе операции, нужные Васе.

Формат входных данных
В первой строке входного файле содержится число n - количество объектов в хранилище Васи (1 <= n <= 10⁵). В i-й из следующих n строк содержится описание свойств объекта с номером i: сначала дано число ki - количество свойств у i-го объекта, а затем через пробел даны ki чисел pi,j - свойства i-го объекта (0 <= k_i <= 100, 1 <= p_i,j <= 10⁹).
Все объекты пронумерованы от 1 до n в порядке, представленном во входных данных. Гарантируется, что общее количество свойств у всех объектов не превосходит 10⁵. Также гарантируется, что для каждого i все pi,j различны.
В n + 2 строке содержится число q - количество запросов к хранилищу Васи (1 <= q <= 10⁵).
В j-й из следующих q строк содержится информация об j-м запросе:
- c, если из хранилища требуется удалить устаревшее свойство c (1 <= c <= 10⁹);
? r, если требуется найти количество оставшихся свойств у объекта с номером r.

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

Два одинаковых массива

Примеры