--->
14 задач
<---
Источники
#112092
Источники:
[
Личные олимпиады,
Открытая олимпиада школьников,
2013-2014,
Заключительный этап,
Задача D
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes
Вова и Марина любят играть в игры, а особенно — придумывать к ним свои правила. Недавно они открыли для себя веселую игру «Чапаев», в которой игроки должны сбивать щелчками шашки вражеского цвета с шахматной доски (также эта игра известна под названием «Щелкунчики»). Вдоволь наигравшись, они решили модифицировать правила, добавив игре математическую сложность.
Теперь они играют в «Чапаева» не на шахматной доске, а на доске в форме дерева! Их дерево состоит из \(N\) вершин. Вершина 1 является корнем дерева, а из каждой из оставшихся вершин проведено ребро в некоторую вершину с меньшим номером — ее непосредственного предка.
В игре участвуют шашки одного цвета, изначально расположенные в некоторых вершинах дерева. За один ход игрок выбирает некоторую шашку и щелчком отправляет ее к корню по ребрам дерева, сбивая при этом с доски все встреченные на пути шашки. Сама шашка, по которой производился удар, после попадания в корень дерева также слетает с доски.
Игроки делают ходы по очереди. Проигрывает тот игрок, к ходу которого на доске не остается шашек.
Придуманная ими игра замечательна также тем, что на одной и той же доске можно играть, начиная с разных начальных позиций шашек. Практика показала, что самые интересные партии получаются, если исходно расставить фишки во все вершины, являющиеся потомками (непосредственными или косвенными) некоторой вершины Root, при этом в саму вершину Root фишка не ставится.
Дети решили сыграть \(N\) партий, перебрав в качестве вершины Root каждую вершину дерева по одному разу. Если у очередной вершины Root нет потомков, и на доске исходно не оказывается ни одной фишки, то игры не происходит, и дети переходят к следующей расстановке. В каждой партии Марина ходит первой.
Вова интересуется у вас, в скольких партиях Марина сможет одержать победу, если игроки будут действовать оптимально.
Формат входного файла
В первой строке находится целое число \(N\) (1 ≤ \(N\) ≤ 500 000) — количество вершин в дереве.
Во второй строке следуют целые числа \(p_2\), \(p_3\), ..., \(p_N\), разделенные пробелами, где \(p_i\) — это номер вершины, являющейся предком вершины \(i\) (1 ≤ pi < i).
Формат выходного файла
Выведите единственное целое число — количество партий, в которых Марина одержит победу.
Комментарий
Разберем тест из условия. Доска для игры показана на рисунках ниже. Дети сыграют четыре партии, выбирая в качестве Root вершины 1, 2, 3 и 5. Если выбрать в качестве Root любую из трех оставшихся вершин, на доске исходно не окажется ни одной фишки, поэтому игры не произойдет.
Если выбрать в качестве Root вершину 5, фишки будут исходно находиться в вершинах 6 и 7. В такой партии Марина проигрывает: после того, как она сбивает любую из этих двух фишек с доски, Вова сбивает оставшуюся и заканчивает партию.
Если выбрать в качестве Root вершину 2 или 3, у Марины будет возможность выиграть игру за один ход, щелкнув по фишке из вершины 4 (при этом, в случае Root = 2, она по пути также собьет фишку из 3 вершины по правилам игры)
Можно убедиться, что если выбрать в качестве Root вершину 1, у Марины также будет выигрышная стратегия. Для этого первым ходом Марина должна сбить фишку из вершины 2. Пример партии с таким начальным расположением показан ниже.
Таким образом, Марина выигрывает в трех партиях
Система оценивания
Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
0. Тест 1. Тест из условия, оценивается в ноль баллов.
1. Тесты 2–17. В тестах этой группы \(N\) ≤ 20. Эта группа оценивается в 20 баллов
2. Тесты 18–38. В тестах этой группы \(N\) ≤ 200. Эта группа оценивается в 20 баллов.
3. Тесты 39–59. В тестах этой группы \(N\) ≤ 5 000. Эта группа оценивается в 20 баллов.
4. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов.
Примеры
Входные данные
7 1 2 3 1 5 5
Выходные данные
3
#113555
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Известно, что в солнечной системе есть 8 планет и один планетоид. Мало кто знает, что ещё есть секретная планета, населенная медведями. Именно туда ассоциация Savez отправляет бравого генерала Хенрика для изучения медведей. Выяснилось, что медведи умеют телепортироваться. Расчётливый генерал Хедрик решил завербовать их в свою армию.
У одного медведя есть N строк (обозначим i -ю из них x i ). Исследования показывают, что количество раз, которое может телепортироваться медведь равно длине наибольшей подпоследовательности этих строк, удовлетворяющей такому правилу: строки x i и x j ( i < j ) могут принадлежать одной такой последовательности, если x i является и префиксом, и суффиксом x j .
Помогите уставшему от долгого полёта генералу Хендрику определить, сколько телепортаций сможет сделать данный медведь.
Входные данные
В первой строке содержится одно целое число N – количество строк, которые есть у медведя. В последующих N строках содержатся сами эти строки. Входной файл содержит не более двух миллионов символов.
Выходные данные
Выведите одно число – ответ на вопрос любопытного генерала Хендрика.
Примечание
В первом примере наибольшая последовательность A -> AA -> AAA В третьем примере наибольшая последовательность A -> A -> A или B -> B -> B
Примеры
Входные данные
5 A B AA BBB AAA
Выходные данные
3
Входные данные
5 A ABA BBB ABABA AAAAAB
Выходные данные
3
Входные данные
6 A B A B A B
Выходные данные
3
ограничение по времени на тест
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
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes
Члены комиссии соревнования ICPC не смогли придумать задачи, поэтому они решили ранжировать команды лексикографически. Таким образом, победителем станет команда, название которой лексикографически самое маленькое. Героиня этой задачи, Этна, является лидером команды, личность которой мы будем скрывать. Название её команды начинается с буквы «Z», что ставит её в довольно плохое положение. После долгих разговоров с комитетом Этна смогла добиться более справедливого способа ранжирования команд. К сожалению, команды будут продолжать сортировать лексикографически, но определение лексикографического порядка изменится. А именно, комитет случайным образом выберет перестановку букв английского алфавита и определит лексикографический порядок, используя эту перестановку. Этна сразу же достала свой ноутбук и написала программу, которая находит перестановку букв для каждой команды, согласно которой эта команда выиграет соревнование. К сожалению, программа еще не закончена. Помогите Этне и напишите более эффективную программу с той же функциональностью.
Входные данные
На первной строке дано натуральное число \(N\), которое обозначает количество команд, участвующих в соревновании.
В следующих \(N\) строках даны названия команд, участвующих в соревновании. Название каждой команды состоит из одного слова, которое в свою очередь состоит из строчных букв английского алфавита. Конечно, названия команд отличаются друг от друга.
Выходные данные
Для каждой команды в исходном порядке необходимо вывести перестановку букв английского алфавита, в соответствии с которой эта команда выиграет соревнование. Если такой перестановки нет, необходимо вывести слово «nemoguce», а если таких перестановок несколько, достаточно вывести любую.
Система оценки
В этой задаче 3 подгруппы. Обозначим \(L\) - суммарную длину строк, \(K\) - количество различных букв.
(13 баллов) \(1 \le N \le 100, 1 \le L \le 10000, 1 \le K \le 6\)
(32 балла) \(1 \le N \le 350, 1 \le L \le 10000, 1 \le K \le 26\)
(55 баллов) \(1 \le N \le 25000, 1 \le L \le 1000000, 1 \le K \le 26\)
Примеры
Входные данные
3 war zag wro
Выходные данные
yxwzvutsqponmlkjihgfedcbar zyxwvutsrqponmlkjihgfedcba yxwzvutsrqponmlkjihgfedcba
Входные данные
3 b ab aa
Выходные данные
zyxwvutsrqponmlkjihgfedcba nemoguce zyxwvutsrqponmlkjihgfedcab
Входные данные
7 bcada dbaab bbabc ababb aacdf bcdff baddb
Выходные данные
zyxwvutsrqponmlkjihgfecbad zyxwvutsrqponmlkjihgfedcba zyxwvutsrqponmlkjihgfebdca nemoguce zyxwvutsrqponmlkjihgfecadb zyxwvutsrqponmlkjihgfecbda nemoguce
Выбрано
:
|