Страница: << 9 10 11 12 13 14 15 >> Отображать по:

#112092

Чапаев на дереве

Темы: [Функция Гранди] [Бор] [Обход в глубину] [Дерево отрезков, RSQ, RMQ] [Множества]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2013-2014, Заключительный этап, Задача D ]

Вова и Марина любят играть в игры, а особенно — придумывать к ним свои правила. Недавно они открыли для себя веселую игру «Чапаев», в которой игроки должны сбивать щелчками шашки вражеского цвета с шахматной доски (также эта игра известна под названием «Щелкунчики»). Вдоволь наигравшись, они решили модифицировать правила, добавив игре математическую сложность.

Теперь они играют в «Чапаева» не на шахматной доске, а на доске в форме дерева! Их дерево состоит из $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

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

#112094

Пиксели торжествуют

Темы: [Обход в глубину]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2013-2014, Заключительный этап, Задача F ]

08.03.2014, Париж, Франция. Дерзкое ограбление совершено в Парижском музее современного искусства. Похищено множество экспонатов, наиболее известный из которых — картина «Пиксели торжествуют» киберкубиста Этьена Бурсье-Мужено.

«Это большая потеря для нас, — заявил директор музея Фабрис Эрготт. — Полиция уже разыскивает преступников, но мы вынуждены признать, что, судя по тому, как легко злоумышленники справились с охранной системой, мы имеем дело с профессионалами экстра-класса и не питаем надежд на возвращение шедевра в нашу коллекцию. Кроме того, уничтожена вся база данных музея, поэтому реставраторы не обладают достаточным количеством информации для восстановления картины. Безусловно, каждый образованный француз знает, что она представляет собой прямоугольник из $H$ x $W$ черных и белых квадратных пикселей ($H$ — высота, а $W$ — ширина картины в пикселях). Но информацию о цвете самих пикселей придется добывать по крупицам».

В свою очередь, представитель Национального архива Франции Армель Ле Гофф поспешила успокоить культурную общественность: «К счастью, архив располагает снимками отдельных фрагментов картины. А именно, в нашем распоряжении имеется информация о $N$ прямоугольных фрагментах (со сторонами, параллельными соответствующим сторонам картины), для каждого из которых известны его координаты $r_1$, $c_1$, $r_2$, $c_2$, а также цвета входящих в него пикселей. Строки картины пронумерованы от 1 до $H$ сверху вниз, столбцы — от 1 до $W$ слева направо, ($r_1$; $c_1$) — номера строки и столбца левого верхнего пикселя фрагмента, ($r_2$; $c_2$) — номера строки и столбца правого нижнего пикселя фрагмента, $r_1$ ≤ $r_2$, $c_1$ ≤ $c_2$. Однако, в силу ряда причин некоторые фрагменты могут храниться в инвертированном виде, то есть все белые пиксели в них заменены на черные, а все черные — на белые, при этом достоверно не известно, какие фрагменты инвертированы. Это серьезно усложняет задачу по восстановлению утерянного шедевра величайшего киберкубиста, поэтому мы обращаемся за помощью ко всему программистскому сообществу. Национальный архив, со своей стороны, готов предоставить все имеющиеся данные о фрагментах картины. Мы отдаем себе отчет в том, что, возможно, картину не удастся восстановить однозначно, поэтому просим найти максимально светлую из всех возможных подходящих картин, то есть содержащую как можно больше белых пикселей: широко известно, что „Пиксели“ являются одним из самых оптимистичных творений Этьена Бурсье-Мужено».

Формат входного файла

Первая строка входного файла содержит два целых числа $H$ и $W$ (1 ≤ $H$ * $W$ ≤ $10^6$) — высоту и ширину картины в пикселях. Вторая строка содержит единственное целое число $N$ (1 ≤ $N$ ≤ $10^6$) — количество фрагментов. Далее содержатся $N$ описаний фрагментов. Первая строка описания — координаты $r_1$, $c_1$, $r_2$, $c_2$ (1 ≤ $r_1$ ≤ $r_2$ ≤ $H$, 1 ≤ $c_1$ ≤ $c_2$ ≤ $W$). Следующие $r_2$ - $r_1$ + 1 строк описания содержат сам фрагмент (возможно, инвертированный): каждая из этих строк состоит из ровно $c_2$ - $c_1$ + 1 нулей и единиц, разделенных пробелами. Нули означают белые пиксели, единицы - черные.

Суммарная площадь всех фрагментов $S$ ≤ $10^6$.

Формат выходного файла

Если подходящей картины не существует, то~есть предоставленные Национальным архивом данные противоречивы, выведите единственное число $-1$.

Иначе в первой строке выходного файла выведите максимальное число нулей, которое могла содержать утерянная картина, а в следующих $H$ строках — искомую картину с максимально возможным количеством нулей в том же формате, что и фрагменты во входном файле: $H$ строк, в каждой из которых $W$ разделенных пробелами нулей и единиц. Если подходящих картин с максимальным числом белых пикселей несколько, выведите любую из них.

Комментарий

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

Система оценивания

Тесты к этой задаче состоят из четырех групп.

0. Тесты 1–2. Тесты из условия, оцениваются в ноль баллов.

1. Тесты 3–27. В тестах этой группы $N$ ≤ 10, $S$ ≤ 1 000, $H$ * $W$ ≤ 1 000. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.

2. Тесты 28–36. В тестах этой группы $N$ ≤ 500, $S$ ≤ 20 000, $H$ * $W$ ≤ 500 000. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой группы.

3. Тесты 37–39. В тестах этой группы $S$ ≤ 20 000, $H$ * $W$ ≤ 500 000. Эта группа оценивается в 4 балла, баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой и второй групп.

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

Примеры

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

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

5
0 1 0 
0 0 0

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

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

-1

#112095

Игорь и игрушки

Темы: [Бинарный поиск в массиве] [Бинарный поиск по ответу] [Тернарный поиск] [Многоугольники. Выпуклые оболочки] [Обход в ширину] [Дерево отрезков, RSQ, RMQ]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2013-2014, Заключительный этап, Задача G ]

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

При входе в магазин у Игоря сразу разбежались глаза. Ему хотелось и гоночную машинку, и кораблик с белыми парусами, и саблю, которая так и манила его своим блестящим лезвием. Всего в магазине продается $N$ новых игрушек, причем так получилось, что все они плоские и имеют форму выпуклых многоугольников (действительно, на что еще можно было надеяться в магазине «Сто тысяч и один выпуклый многоугольник для детей младшего школьного возраста»?). Но строгий отец сказал, что купит Игорю только две игрушки. Игорь сразу же начал перебирать в голове варианты, но их оказалось слишком много, а если быть более конкретным, то его интересовало ровно $Q$ вариантов выбора пары игрушек.

Любознательный Игорь сразу же задумался о тонкостях упаковки игрушек. А именно, для каждой интересующей его пары игрушек $i$, $j$ он хочет проделать следующие операции.

Изначально каждая игрушка лежит в своей плоской прямоугольной коробке, которая плотно прилегает к игрушке. Далее Игорь ставит эти две коробки на стол рядом друг с другом ($i$-ю игрушку можно поставить как левее $j$-й, так и правее), убирает коробки, потом придвигает игрушки друг к другу, насколько это возможно, и кладет то, что получилось, обратно в коробку (обратите внимание на рисунок). Так как Игорь очень экономный, ему нужно знать размеры получившейся коробки. Повлиять на высоту итоговой коробки, двигая игрушки параллельно плоскости стола, нельзя, так что вам нужно помочь Игорю лишь с определением минимально возможной ширины получившейся коробки.

Обратите внимание, что игрушки можно лишь двигать параллельно плоскости стола, поворачивать их каким-либо образом запрещено. Таким образом, задачу можно считать двумерной: ось $O_x$ совпадает с плоскостью стола, а ось $O_y$, по которой измеряется высота игрушек и коробок, перпендикулярна плоскости стола. Стороны коробок параллельны соответствующим осям координат. Диковинных игрушек в магазине предостаточно, так что они могут «стоять» на столе, в том числе и балансируя на одной вершине самым непостижимым образом.

Для лучшего понимания условия ознакомьтесь с примером и иллюстрациями к нему.

Формат входного файла

В первой строке содержится натуральное число $N$ (1 ≤ $N$ ≤ 100 000) - количество игрушек. Далее следуют описания $N$ выпуклых многоугольников в следующем формате: сначала идет натуральное число $k_m$ (3 ≤ $k_m$ ≤ 300 000) - количество вершин в $m$-м многоугольнике, затем идут $k_m$ строк, в которых записаны пары целых чисел x_m,s, y_m,s, по модулю не превосходящих $10^9$ - координаты вершин $m$-го многоугольника в порядке обхода против часовой стрелки, заданные в системе координат соответствующей ему коробки, которая стоит на столе (это означает, что y_m,s >= 0, а также для всех игрушек существует вершина $v_m$, у которой y_{m,$v_m$} = 0). Сумма всех $k_m$ (обозначим ее за $S$) не превосходит 300 000.

В следующей строке записано натуральное число $Q$ (1 ≤ $Q$ ≤ 500 000) - число вариантов. Следующие $Q$ строк содержат пары натуральных чисел $i_t$, $j_t$ (1 ≤ $i_t$ < $j_t$ ≤ $N$) - номера сдвигаемых игрушек в очередном варианте.

Формат выходного файла

Выведите $Q$ строк: для каждого варианта выбора пары одно вещественное число - необходимую ширину коробки. Ответ будет считаться правильным, если все числа посчитаны с абсолютной или относительной погрешностью не более $10^{-9}$.

Комментарий

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

Система оценивания

Тесты к этой задаче состоят из четырех групп.

0. Тест 1. Тест из условия, оценивается в ноль баллов.

1. Тесты 2–20. В тестах этой группы $k_m$ ≤ 100, $Q$ ≤ 1 000, $S$ ≤ 10 000. Эта группа оценивается в 25 баллов. Баллы начисляются только при прохождении всех тестов группы.

2. Тесты 21–40. В тестах этой группы $k_m$ ≤ 300, $Q$ ≤ 50 000, $S$ ≤ 100 000. Эта группа оценивается в 25 баллов. Баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае про- хождения всех тестов из первой группы.

3. Тесты 41–65. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 50 баллов. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой и второй групп. Тесты в этой группе оцениваются независимо.

Примеры

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

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

14.5000000000

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

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

21.0000000000

#112335

Автомат с игрушками

Темы: [Обход в глубину]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2014, 1 тур, Автомат с игрушками ] [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2014, 1 тур, Задача A ]

В развлекательном центре $Е$-города был установлен игровой автомат нового поколения. В автомат можно бросить монету и следить за её продвижением сверху вниз по разветвляющемуся лабиринту из трубок. В лабиринте есть n узлов, которые пронумерованы числами от 1 до $n$. При бросании монета попадает в первый узел. Каждый узел лабиринта, кроме первого, имеет одну входящую сверху трубку, по которой монета может в него попасть. Из каждого узла выходит не более двух трубок, идущих вниз, одна из которых ведет налево, а другая — направо. Каждая трубка имеет некоторую ширину. Монета проваливается в более широкую трубку, а в случае равенства ширины трубок — в левую.

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

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

Панкрату понравилась игрушка, которая находится в узле с номером $v$.

Требуется написать программу, которая определяет, сколько монет должен бросить в автомат Панкрат, чтобы получить игрушку из узла $v$.

Формат входного файла

В первой строке входного файла задано число $n$ — количество узлов в лабиринте. В последующих n строках заданы описания всех узлов, в $k$-й из этих строк описан узел с номером $k$.

Описание k-го узла состоит из четырех целых чисел: $a_k$, $u_k$, $b_k$, $w_k$. Если из $k$-го узла выходит левая трубка, то $a_k$ — номер узла, в который она ведет ($k$ < $a_k$ <= $n$), а $u_k$ — её ширина. Если левой трубки нет, то $a_k$ = $u_k$ = 0. Если из $k$-го узла выходит правая трубка, то $b_k$ — номер узла, в который она ведет ($k$ < $b_k$ <= $n$), а $w_k$ — её ширина. Если правой трубки нет, то $b_k$ = $w_k$ = 0.

В последней строке задано целое число $v$ (1 <= $v$ <= $n$) — номер узла, в котором находится игрушка, понравившаяся Панкрату.

Гарантируется, что во все узлы, кроме первого, входит ровно одна трубка

Формат выходного файла

Выходной файл должен содержать одно число — количество монет, которое необходимо бросить в автомат Панкрату, чтобы получить игрушку, которая находится в узле $v$. Если получить выбранную игрушку невозможно, выведите число −1.

Система оценки

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

Подзадача 1

1 <= $n$ <= 100

1 <= $u_k$; $w_k$ <= 300

Подзадача оценивается в 50 баллов.

Подзадача 2

1 <= $n$ <= $10^5$

1 <= $u_k$; $w_k$ <= $10^9$

Подзадача оценивается в 50 баллов.

Пояснения к примеру

В первом примере первая монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 1, 3 и 4:

Вторая монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 2 и 6:

Третья монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 5 и 7:

Примеры

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

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

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

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

-1

#112589

Министерство

Темы: [Алгоритмы на графах] [Хеш]

Источники: [ Личные олимпиады, Central European Olympiad in Informatics , Central European Olympiad in Informatics 2007, Министерство ]

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

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

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

Есть два особых случая:

Департамент, в котором должностное лицо — сам министр, тогда этот департамент есть всё министерство.
Департамент, в котором у должностного лица нет ни одного подчинённого.

Высотой департамента назовем длину максимальной последовательность сотрудников x ₁ , ..., x _d такую, что сотрудник x _i является начальником сотрудника x _{i

+ 1} для всех 1 ≤ i < d . Заметим что высота департамента, состоящего из одного сотрудника равна 1 .

Два департамента A и B совпадают, если существует взаимно-однозначное отображение, сопоставляющее каждому сотруднику x _A из департамента A сотрудника x _B из департамента B , таким образом, что сотрудник x _A является начальником сотрудником y _A , тогда и только тогда, когда x _B является начальником y _B . Заметим, что если два департамента совпадают, то они имеют одинаковую высоту, одинаковое количество сотрудников и начальнику первого департамента соответствует начальник второго.

На приведенных картинках департаменты A и B совпадают, а C не совпадает ни с A , ни c B .

$\text{[math]}$

Вам необходимо для каждой высоты вычислить количество различных департаментов имеющих такую глубину. Формально требуется построить последовательность n ₁ , ..., n _d , где d это высота всего министерства, а n _i — количество различных департаментов высоты i .

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

Входной файл содержит единственную строку, которая описывает иерархическую структуру министерства, используя следующую нотацию. Каждый департамент кодируются строкой "( x ₁ ... x _k )", где k — количество подчинённых у начальника департамента, а строки x _i — коды им подчиняющихся департаментов. Департамент, состоящий из одного человека, кодируется строкой "()". Структура министерства задается кодом всего министерства. Количество сотрудников министерства не превосходит 1 000 000 (включая министра).

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

Выходной файл должен содержать d строк, где d это высота министерства. i -ая строка должна содержать количество различных департаментов высоты i .

Примечание

Приведенная картинка иллюстрирует пример из условия. $\text{[math]}$

Примеры

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

(((())())((()())(()()()))(()(())))

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

Страница: << 9 10 11 12 13 14 15 >> Отображать по:

Выбрано

Отменить

Добавить в контест