--->
35 задач
<---
Источники
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
512 megabytes
Компания « Rapid City Dynamics » знаменита её роботами-собаками, роботами-гепардами и даже человекоподобными роботами. Но большие проекты требуют больших денег, так что компания решила создать что-то простое, но популярное (и более востребованное). Так что компания разрабатывает нового робота « Rat-O-Matic », и вы, как работник « Rapid City Dynamics », принимаете участие в этом.
Робот выглядит как механическая крыса, которая может двигаться и генерировать мелодию, наступая на специальные рамки. Плоскость бесконечна во все стороны, и на ней задана декартова система координат.
Есть ровно n рамок. Каждая рамка задана тремя числами: x , y и r . Она задаёт территорию, ограниченую между двух квадратов со сторонами параллельным осям координат и центрами в точке ( x , y ): радиус первого квадрата r , а второго — 2· r . Радиус квадрата — это расстояние между его центром и стороной. Ко всему прочему, каждой рамке соответствует своя нота. Сейчас есть только 3 возможных ноты, обозначим их как « r », « a » и « t ».
Гарантируется, что никакие две рамки не касаются и не пересекаются.
Вы можете взаимодействовать с роботом, вбивая номер рамки на специальной клавиатуре (рамки пронумерованы начиная с 1 ). Изначально, крыса находится снаружи всех рамок. Благодаря патентованной системе навигации, робот выбирает путь до рамки, который пересекает минимальное количество рамок. Когда крыса наступает на рамку в первый раз, соответствующая нота добавляется в мелодию. Робот останавливается после того, как наступит на нужную рамку.
Известно, что людям нравятся похожие мелодии. В вашей базе данных имеются m мелодий. Каждая мелодия задаётся строкой из символов, которая задаёт ноты. Мелодия, сгенерированная крысой, содержится в мелодии из базы данных, если она содержится в ней в качестве подстроки. Популярность сгенерированной мелодии - это число мелодий в базе данных, которые содержат её. Одинаковые мелодии из базы данных должны быть учтены несколько раз.
В попытке создания самого классного расположения рамок, вы совершили q экспериментов. Эксперименты бывают трёх типов:
- Выключить рамку x . Гарантируется, что рамка была включена до этой операции. Выключенные рамки не влияют на мелодию крысы. Вначале все рамки включены.
- Включить рамку x . Гарантируется, что рамка была выключена до этой операции.
- Посчитать популярность мелодии, сгенерированной роботом при движении от точки с координатами ( 10 9 , 10 9 ) до рамки x . Гарантируется, что рамка x является включённой.
Твоя задача — провести эти эксперименты, используя только свой компьютер!
Входные данные
В первой строке содержится натуральное число n — количество рамок ( 1 ≤ n ≤ 2·10 5 ).
В следующих
n
строках описаны рамки,
i
-я из них содержит три натуральных числа
x
i
,
y
i
,
r
i
и символ
c
i
, разделённые пробелами (
- 10
8
≤
x
i
,
y
i
≤ 10
8
,
1 ≤
r
i
≤ 10
8
, и
c
i
{«
r
», «
a
», «
t
»} — координаты центра рамки, радиус внутреннего квадрата и её нота, соответственно.
Следующая строка содержит натуральное число m — количество мелодий в базе ( 1 ≤ m ≤ 2·10 5 ).
Следующие m строк содержат непустые строки из букв « r », « a » или « t », которые задают мелодии. Суммарная длина всех строк не превосходит 2·10 5 .
Следующая строка содержит натуральное число q — количество экспериментов ( 1 ≤ q ≤ 2·10 5 ).
Следующие q строк описывают эксперименты, j -я из них содержит символ t j (« - », « + » или « ? ») и натуральное число x j отделённое пробелом. Символ задаёт тип эксперимента (« - » — 1, « + » — 2 и « ? » — 3), а число обозначает номер рамки.
Гарантируется, что есть хотя бы один эксперимент третьего типа.
Выходные данные
Для каждого эксперимента третьего типа, выведите одно число — популярность получившейся мелодии.
Группы тестов (Все группы независимы)
10 баллов — (1 ≤ n, m, q ≤ 100, суммарная длина строк не превосходит 100, тесты 2-6) .
10 баллов — ( 1 ≤ n ≤ 4 000, 1 ≤ m, q ≤ 100, суммарная длина строк не превосходит 100, тесты 7-9) .
10 баллов — ( 1 ≤ n, q ≤ 100, 1 ≤ m ≤ 200 000 , суммарная длина строк не превосходит 200 000, тесты 10-13) .
10 баллов — ( 1 ≤ n ≤ 4 000, 1 ≤ m ≤ 200 000, 1 ≤ q ≤ 100, суммарная длина строк не превосходит 200 000, тесты 14-16) .
10 баллов — ( 1 ≤ n ≤ 200 000, 1 ≤ m, q ≤ 100, суммарная длина строк не превосходит 100, тесты 17-19) .
15 баллов — ( 1 ≤ n, q ≤ 200 000, 1 ≤ m ≤ 100, суммарная длина строк не превосходит 100, тесты 20-23) .
35 баллов — полные ограничения, тесты 24-57.
Примеры
Входные данные
3 3 3 4 r 2 4 1 a 14 4 1 t 3 rat rara aaa 6 ? 3 ? 2 - 1 ? 2 + 1 ? 2
Выходные данные
1 2 3 2
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Знаменитый художник Вася только что закончил работу над своим новым шедевром и хочет знать, сколько он сможет получить за свой труд.
Картина представляет собой прямоугольник N на M сантиметров, разделенный на маленькие квадратики 1 на 1 сантиметр со сторонами, параллельными сторонам картины. Для достижения гармонии каждый из этих квадратиков Вася покрасил одним из 26 особых цветов, обозначаемых маленькими латинскими буквами.
Стоимость картины в точности равна количеству «симпатичных» частей в ней. Частью картины называется любой прямоугольник, который может быть вырезан из нее по границам квадратиков. Часть называется «симпатичной», если при выполнении симметрии относительно ее центра получается прямоугольник, раскрашенный также, как и исходная часть. Например, в картине, раскрашенной так:
abc
acb
симпатичными являются все части, состоящие из одного квадратика (их 6), а также части
bc acb и a
Напишите программу, которая по информации о шедевре Васи определит его стоимость.
Входные данные
В первой строке содержатся два числа N и M ( 1 ≤ N , M ≤ 300 ). В следующих N строках идут строки, состоящие из M маленьких латинских символов. Символ в i -й строке j -м столбце определяет цвет соответствующего квадратика картины.
Выходные данные
Выведите стоимость шедевра — количество частей, симметричных относительно своего центра.
Система оценки
n, m < 10 -> 20 баллов
n, m < 50 -> 30 баллов
n, m < 100 -> 20 баллов
n, m < 300 -> 30 баллов
Примечание
Этот пример разобран в условии
Симпатичными являются шесть частей 1 × 1 , одна часть 1 × 2 и сама картина.
Примеры
Входные данные
2 3 abc acb
Выходные данные
8
Входные данные
3 2 ab cc ba
Выходные данные
8
#113932
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
512 megabytes
Скажем, что последовательность строк t 1 , ..., t k является путешествием длины k , если для всех i > 1 t i является подстрокой t i - 1 строго меньшей длины. Например, { ab , b } является путешествием, а { ab , c } или { a , a } — нет.
Определим путешествие по строке s как путешествие t 1 , ..., t k , все строки которого могут быть вложены в s так, чтобы существовали (возможно, пустые) строки u 1 , ..., u k + 1 , такие, что s = u 1 t 1 u 2 t 2 ... 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 } .
Примеры
Входные данные
7 abcdbcc
Выходные данные
3
Входные данные
4 bbcb
Выходные данные
2
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
256 megabytes
Мы создали бесконечный кроссворд, взяв прямоугольник размера \(\)\(N \times M\)\(\), заполненный буквами и замостили им бесконечную плоскость. Например, прямоугольник
hsin
...hsinhsinhsinhsin...
...honihonihonihoni...
...hsinhsinhsinhsin...
В данном кроссворде нами случайно (равновероятно) выбирается одна клетка и одно из восьми направлений. Затем начиная с данной клетки в данном направлении выписывается слово длины \(\)\(K\)\(\). Описанный процесс повторяется (независимо от первого раза) второй раз. Вам требуется вычислить вероятность того, что два выписанных слова совпадут.
Входные данные
Первая строка содержит три числа \(\)\(M, N, K\)\(\) (\(\)\(1 \leq N, M \leq 500\)\(\), \(\)\(1 \leq K \leq 10^9\)\(\)) — размеры блока и длина выбираемого слова соответственно.
Следующие \(\)\(M\)\(\) строк содержат по \(\)\(N\)\(\) латинских строчных букв, задавая блок, коим замощается доска. Гарантируется, что в данных есть хотя бы две различные буквы.
Выходные данные
Выведите требуемую вероятность в виде сокращённой дроби «p/q» без пробелов и кавычек.
Система оценки
Решение, правильно работающее на тестах, в которых \(\)\(N = M\)\(\) будет оцениваться в \(\)\(62\)\(\) балла.
Примеры
Входные данные
1 2 2 ab
Выходные данные
5/16
Входные данные
2 4 3 honi hsin
Выходные данные
19/512
Входные данные
3 3 10 ban ana nab
Выходные данные
2/27
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
В рамках новой рекламной кампании некоторая корпорация хочет разместить свой логотип где-нибудь в городе. Компания собирается потратить весь рекламный бюджет на логотип, поэтому он должен быть воистину огромным. Один из менеджеров решил использовать здания целиком как части логотипа.
Логотип состоит из \(n\) вертикальных полос различной высоты. Полосы пронумерованы от \(1\) до \(n\) слева направо. Логотип описывается перестановкой \((s_1, s_2, ..., s_n)\) чисел \(1, 2, ..., n\). Полоса с номером \(s_1\) - самая низкая, полоса с номером \(s_2\) - следующая по высоте и, наконец, полоса \(s_n\) - самая высокая. Фактическая высота полос не имеет большого значения. Вдоль главной улицы расположено \(m\) зданий. К вашему удивлению, высота зданий различна. Задача состоит в том, чтобы найти все позиции, на которых логотип соответствует зданиям. Помогите компании и найдите все непрерывные последовательности зданий, которые соответствуют логотипу. Непрерывная последовательность зданий соответствует логотипу, если здание \(s_1\) в этой последовательности является самым низким, здание \(s_2\) является следующим по высоте и т. д. Например, последовательность зданий высотой \(5, 10, 4\) соответствует логотипу, описанному перестановкой \((3, 1, 2)\), поскольку здание №3 (высотой 4) является самым низким, здание №1 - вторым по высоте, а здание №2 - самым высоким.
Входные данные
Первая строка стандартного ввода содержит два целых числа \(n\) и \(m\) \((2 \le n \le m \le 1 000 000)\).
Вторая строка содержит \(n\) целых чисел \(s_i\), образующих перестановку чисел \(1, 2, ..., n\). То есть \(1 \le s_i \le n\) и s\(_i \neq s_j\) для \(i \neq j\).
Третья строка содержит \(m\) целых чисел \(h_i\) - высоты зданий (\(1 \le h_i \le 10^9\) для \(1 \le i \le m\)). Все числа различные.
В каждой строке числа разделены пробелами.
Выходные данные
Первая строка стандартного вывода должна содержать целое число \(k\) – количество совпадений.
Вторая строка должна содержать \(k\) целых чисел - индексы зданий начиная с 1, которые соответствуют первой полосе из логотипа в правильном соответствии. Числа должны быть перечислены в возрастающем порядке.
Если \(k = 0\), ваша программа должна напечатать пустую вторую строку.
Система оценки
В тестах суммарной стоимостью не менее 35 баллов \(n \le 5000\) и \(m \le 20 000\).
В тестах суммарной стоимостью не менее 60 баллов \(n \le 50 000\) и \(m \le 200 000\).
Примеры
Входные данные
5 10 2 1 5 3 4 5 6 3 8 12 7 1 10 11 9
Выходные данные
2 2 6
Выбрано
:
|