На отдыхе в Теплой Стране Вера познакомилась с симпатичным волейболистом- трактористом Петром. Турист Петр, кстати, собирается после отличного отдыха в Теплой Стране отправиться в путешествие по городам Европы. Как известно, Европа обладает развитой транспортной системой: в Европе есть \(V\) интересующих Петра городов и \(E\) маршрутов ночных поездов. Каждый маршрут соединяет два различных города, время в пути составляет одну ночь. Поезда по маршруту ходят в обоих направлениях.
Основной целью поездки Петра является осмотр местных достопримечательностей. По- скольку Петр — невероятно занятой человек, то он решил, что все путешествие должно занимать не более четырех дней. Петр уже многое повидал, поэтому на осмотр достопримечательностей в каждом городе Петр тратит ровно один день. Он хочет составить наиболее практичный тур: каждый день он будет тратить на осмотр города, а каждую ночь — на переезд ночным поездом между городами. Разумеется, Петр не имеет ни малейшего желания посещать один город несколько раз.
Но на этом прагматичность Петра не заканчивается: Петр, как настоящий турист, хочет посмотреть на самые красивые европейские достопримечательности. Он долго изучал справочники и для каждого города оценил свою ожидаемую радость от его посещения \(p_i\). Теперь он хочет найти маршрут, при котором его радость будет наибольшей. Помогите Петру найти такой маршрут.
В первой строке входных данных заданы два целых числа \(V\) и \(E\) (1 ≤ \(V\); \(E \le 3*10^5\)) — количество городов и маршрутов поездов, соответственно. В следующей строке заданы V целых чисел \(p_i\) (1 ≤ \(p_i\) ≤ \(10^8\)), где \(p_i\) обозначает ожидаемую радость от посещения го- рода с номером \(i\). В следующих \(E\) строках заданы описания маршрутов поездов. Каждое описание состоит из пары различных чисел \(a_i\) и \(b_i\) (1 ≤ \(a_i\); \(b_i\) ≤ V\( \)) — номеров городов, между которыми курсирует этот маршрут поезда. Гарантируется, что между каждой парой городов существует не более одного маршрута поезда.
В первой строке выходных данных выведите число K (1 ≤ K ≤ 4) — количество городов в оптимальном маршруте туриста Петра. В следующей строке выведите номера этих городов в порядке посещения. Города нумеруются начиная с единицы. Если оптимальных маршрутов несколько, выведите любой из них.
Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
0. Тесты 1–2. Тесты из условия, оцениваются в ноль баллов.
1. Тесты 3–16. В тестах этой группы \(V\); \(E\) ≤ 100. Эта группа оценивается в 20 баллов
2. Тесты 17–32. В тестах этой группы \(V\); \(E\) ≤ 1 000. Эта группа оценивается в 20 баллов.
3. Тесты 33–53. В тестах этой группы \(V\) ≤ 3 000, \(E\) ≤ 60 000. Эта группа оценивается в 30 баллов.
4. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 30 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура.
5 4 4 2 3 1 5 1 2 2 3 3 4 4 5
4 2 3 4 5
4 3 1 2 3 4 1 2 1 3 1 4
3 4 1 3
Пафнутий и его друзья — большие любители разнообразных настольных игр. Особенно им нравятся игры, требующие как можно быстрее производить в уме непростые вычисления, поэтому абсолютным хитом их вечерних посиделок в аудиториях НУОП (Неизвестного университета олимпиадного программирования) стала игра «Шустрая черепашка». В комплект игры входят:
* Клетчатое поле из \(N\) рядов по \(M\) клеток. Каждая клетка поля либо свободна, либо блокирована для перемещения.
* Q игровых карточек. Каждая карточка содержит описание множества стартовых клеток A, множества дополнительно блокируемых клеток B и множества конечных клеток C. Множества A, B и C непусты, попарно не пересекаются и состоят из свободных клеток.
* Маленькая фишка в форме черепашки.
Правила игры очень просты. Игроки последовательно разыгрывают игровые карточки. Как только открывается очередная карточка, игрокам необходимо вычислить, сколько существует хороших троек клеток (\(a_i b_j c_k)\), где \(a_i \in A\), \(b_j \in B\), \(c_k \in C\). Тройка клеток называется хорошей, если можно провести черепашку из стартовой клетки ai в конечную клетку \(c_k\), не посещая при этом клетку \(b_j\). На перемещение черепашки наложено три условия:
1. Черепашка имеет право перемещаться только вниз и вправо в пределах поля.
2. Находиться на блокированных клетках запрещено
3. Клетка \(b_j\) также блокируется для перемещения
Так как таблицу с правильными ответами создатели не включили в комплект, в пылу игры постоянно возникают споры о правильности того или иного значения. Для установления истины ребята попросили вас посчитать ответы для данного комплекта.
Первая строка входного файла содержит два целых числа \(N\) и \(M\) (1 ≤ \(N\), \(M\) ≤ 150) — количество строк и столбцов игрового поля.
Следующие \(N\) строк по \(M\) символов описывают игровое поле в порядке следования сверху вниз, слева направо. Символ ‘.’ соответствует свободной клетке, а ‘#’ — занятой. Строки нумеруются от 1 до \(N\), столбцы — от 1 до \(M\)
Следующая строка содержит целое число \(Q\) (1 ≤ \(Q\) ≤ 100 000) — количество игровых карточек.
Далее следуют \(Q\) блоков, описывающих карточки. Каждый блок состоит из трех строк, описывающих множества \(A\), \(B\) и \(C\) соответственно. Первое число описания определяет размер соответствующего множества, после чего перечисляются его клетки. Каждая клетка задается двумя числами — номером строки и номером столбца. Все клетки в описании различны. Смотрите комментарии к примеру для лучшего понимания формата входных данных.
Гарантируется, что все множества непусты, все клетки всех множеств являются свободными и никакая клетка не принадлежит более чем одному множеству из какой-то карточки.
В выходной файл выведите ровно \(Q\) чисел по одному на строке — правильные ответы на карточки в порядке их следования во входном файле.
В приведенном примере игровой комплект содержит две карточки
Во всех тройках первой карточки черепашка стартует в верхнем левом углу и финиширует в правом нижнем. Несложно видеть, что это возможно сделать, только если из трех элементов множества \(B\) блокируется первая клетка второй строки, то есть хорошей тройкой является \((1, 1) - (2, 1) - (5, 6)\).
На второй карточке хорошими являются тройки: \((1, 2) - (3, 1) - (5, 6)\), \((2, 1) - (3, 1) - (5, 6)\), \((2, 1) - (3, 3) - (5, 1)\).
Тесты к этой задаче состоят из четырех групп
0. Тест 1. Тест из условия, оценивается в ноль баллов.
1. Тесты 2–18. В тестах этой группы \(N\) ≤ 100, \(Q\)total ≤ 1 000. Эта группа оценивается в 30 баллов. Баллы начисляются только при прохождении всех тестов группы.
2. Тесты 19–32. В тестах этой группы \(N\) ≤ 100, \(Q\)total ≤ 1 000 000. Эта группа оценивается в 30 баллов. Баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой группы.
3. В тестах этой группы дополнительные ограничения отсутствуют, однако гарантируется, что \(N\) и \(Q\)total будут равномерно возрастать с номером теста. Эта группа оценивается в 40 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура, причем только в случае прохождения всех тестов из первой и второй групп. Тесты в этой группе оцениваются независимо.
5 6 ..##.. ....#. .#.#.. .#...# ..#... 2 1 1 1 3 2 1 2 3 4 3 1 5 6 2 1 2 2 1 2 3 1 3 3 2 5 1 5 6
1 3
Вова и Марина любят играть в игры, а особенно — придумывать к ним свои правила. Недавно они открыли для себя веселую игру «Чапаев», в которой игроки должны сбивать щелчками шашки вражеского цвета с шахматной доски (также эта игра известна под названием «Щелкунчики»). Вдоволь наигравшись, они решили модифицировать правила, добавив игре математическую сложность.
Теперь они играют в «Чапаева» не на шахматной доске, а на доске в форме дерева! Их дерево состоит из \(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
Вера очень любит сочинять сказки. С детства она обладала очень богатой фантазией, ее работы были высоко оценены на многочисленных творческих конкурсах, а ее вырази- тельная речь способна невероятно точно передавать эмоции и чувства. Однако, Вера не смогла придумать красивую историю для следующей задачи по программированию:
Дан массив из целых чисел \(a_1\), \(a_2\), . . . , \(a_N\), каждый элемент которого по абсолютной величине не превосходит 2. Найдите такой непустой подотрезок \(a_l\), \(a_l\)+1, . . . , \(a_r\) этого массива (1 ≤ \(l\) ≤ \(r\) ≤ \(N\)), что произведение чисел \(a_l * a_{l+1} * ... * a_r\) является максимально возможным.
Вы, разумеется, можете посостязаться с Верой в креативности, однако мы рекомендуем вам заняться решением задачи.
В первой строке входных данных содержится число \(N (1 \le N \le 200 000)\) — число элементов массива. В следующей строке содержатся \(N\) целых чисел \(a_i\) — элементы массива \((|a_i| \le 2\)).
В единственной строке выходных данных выведите два числа \(l\) и \(r\) — искомые границы оптимального отрезка (1 ≤ \(l\) ≤ \(r\) ≤ \(N\)). В случае, если ответов несколько, выведите любой из них.
Тесты к этой задаче состоят из четырех групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп
0. Тесты 1–3. Тесты из условия, оцениваются в ноль баллов.
1. Тесты 4–15. В тестах этой группы \(N \le 60\). Эта группа оценивается в 30 баллов
2. Тесты 15–31. В тестах этой группы \(N \le 2000\). Эта группа оценивается в 30 баллов.
3. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов.
5 1 -1 2 2 1
3 5
3 -1 0 -2
2 2
7 -1 -2 -1 -2 1 2 -2
2 7
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 баллов. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой, второй и третьей групп. Тесты в этой группе оцениваются независимо.
2 3 3 1 1 1 2 0 1 1 2 2 2 0 1 1 3 2 3 1 1
5 0 1 0 0 0 0
2 3 2 1 2 2 3 0 1 1 0 1 1 1 3 0 1 1
-1