Ивица — страстный компьютерщик. Недавно он начал работать над своей первой компьютерной игрой — клоном популярного тетриса. Хотя игра далека от завершения, его программа уже поддерживает размещение в матрице N × M пяти разных фигур Тетриса (показанных на изображении ниже) в матрице. Перед тем, как поместить фигуру в матрицу, её можно поворачивать на 90 градусов произвольное число раз и можно окрашивать. Кроме того, текущая версия игры не поддерживает размещение фигуры, если она при этом выходит за границы матрицы или перекрывается с другими существующими фигурами в матрице.
Пока Ивица учился в школе, его сестра Марика начала игру и случайным образом повернула, покрасила и поместила фигуры, но таким образом, что соседние фигуры окрашены по-разному. Две фигуры смежны, если они имеют общую сторону или общий угол.
Он хочет знать для каждого из пяти типов фигуры, сколько таких фигур его сестра разместила в матрицу, пока он занят улучшением игры.
Первая строка ввода содержит положительные целые числа N и M ( 1 ≤ N , M ≤ 10 ), которые представляют количество строк и столбцов матрицы Тетриса. Каждая из следующих N строк содержит M символов, которые представляют матрицу. Каждый символ может быть « . », что означает пустую клетку или строчной буквой английского алфавита, которая представляет часть фигуры. Различные буквы представляют разные цвета, а клетки одной фигуры имеют одинаковый цвет.
Гарантируется, что вводная матрица могла быть получена последовательным добавлением фигур Тетриса в изначально пустую матрицу.
Вы должны вывести ровно пять строк. i -я строка должна содержать количество фигур i -го типа, находящихся в данной матрице.
4 5 aaaa. .bb.. .bbxx ...xx
2 1 0 0 0
4 5 .aab. aabb. .cbaa cccaa
1 0 1 1 1
5 7 .c..... ccdddd. caabbcc aabbacc ...aaa.
1 1 2 1 1
У компании BigData Inc. есть n дата-центров, пронумерованных от 1 до n , расположенных по всему миру. В этих дата-центрах хранятся данные клиентов компании (как можно догадаться из названия — большие данные!)
Основой предлагаемых компанией BigData Inc. услуг является гарантия возможности работы с пользовательскими данными даже при условии выхода какого-либо из дата-центров компании из доступности. Подобная гарантия достигается путём использования двойной репликации данных. Двойная репликация — это подход, при котором любые данные хранятся в двух идентичных копиях в двух различных дата-центрах.
Про каждого из m клиентов компании известны номера двух различных дата-центров c i , 1 и c i , 2 , в которых хранятся его данные.
Для поддержания работоспособности дата-центра и безопасности данных программное обеспечение каждого дата-центра требует регулярного обновления. Релизный цикл в компании BigData Inc. составляет один день, то есть новая версия программного обеспечения выкладывается на каждый компьютер дата-центра каждый день.
Обновление дата-центра, состоящего из множества компьютеров, является сложной и длительной задачей, поэтому для каждого дата-центра выделен временной интервал длиной в час, в течение которого компьютеры дата-центра обновляются и, как следствие, могут быть недоступны. Будем считать, что в сутках h часов. Таким образом, для каждого дата-центра зафиксировано целое число u j ( 0 ≤ u j ≤ h - 1 ), обозначающее номер часа в сутках, в течение которого j -й дата-центр недоступен в связи с плановым обновлением.
Из всего вышесказанного следует, что для любого клиента должны выполняться условия u c i , 1 ≠ u c i , 2 , так как иначе во время одновременного обновления обоих дата-центров, компания будет не в состоянии обеспечить клиенту доступ к его данным.
В связи с переводом часов в разных странах и городах мира, время обновления в некоторых дата-центрах может сдвинуться на один час вперёд. Для подготовки к непредвиденным ситуациям руководство компании хочет провести учения, в ходе которых будет выбрано некоторое непустое подмножество дата-центров, и время обновления каждого из них будет сдвинуто на один час позже внутри суток (то есть, если u j = h - 1 , то новым часом обновления будет 0 , иначе новым часом обновления станет u j + 1 ). При этом учения не должны нарушать гарантии доступности, то есть, после смены графика обновления должно по-прежнему выполняться условие, что данные любого клиента доступны хотя бы в одном экземпляре в любой час.
Учения — полезное мероприятие, но трудоёмкое и затратное, поэтому руководство компании обратилось к вам за помощью в определении минимального по размеру непустого подходящего подмножества дата-центров, чтобы провести учения только на этом подмножестве.
В первой строке находятся три целых числа n , m и h ( 2 ≤ n ≤ 100 000 , 1 ≤ m ≤ 100 000 , 2 ≤ h ≤ 100 000 ) — число дата-центров компании, число клиентов компании и количество часов в сутках.
Во второй строке вам даны n чисел u 1 , u 2 , ..., u n ( 0 ≤ u j < h ), j -е из которых задаёт номер часа, в который происходит плановое обновление программного обеспечения на компьютерах дата-центра j .
Далее в m строках находятся пары чисел c i , 1 и c i , 2 ( 1 ≤ c i , 1 , c i , 2 ≤ n , c i , 1 ≠ c i , 2 ), задающие номера дата-центров, на которых находятся данные клиента i .
Гарантируется, что при заданном расписании обновлений в дата-центрах любому клиенту в любой момент доступна хотя бы одна копия его данных.
В первой строке выведите минимальное количество дата-центров k ( 1 ≤ k ≤ n ), которые должны затронуть учения, чтобы не потерять гарантию доступности. Во второй строке выведите k различных целых чисел — номера кластеров x 1 , x 2 , ..., x k ( 1 ≤ x i ≤ n ), на которых в рамках учений обновления станут проводиться на час позже. Номера кластеров можно выводить в любом порядке.
Если возможных ответов несколько, разрешается вывести любой из них. Гарантируется, что хотя бы один ответ, удовлетворяющий условиям задачи, существует.
Тесты к этой задаче состоят из трёх групп. Баллы за каждую группу ставятся только при про- хождении всех тестов группы и всех тестов предыдущих групп.
Рассмотрим первый тест из условия. Приведённый ответ является единственным способом провести учения, затронув только один дата-центр. В таком сценарии третий сервер начинает обновляться в первый час дня, и никакие два сервера, хранящие данные одного и того же пользователя, не обновляются в один и тот же час.
С другой стороны, например, сдвинуть только время обновления первого сервера на один час вперёд нельзя — в таком случае данные пользователей 1 и 3 будут недоступны в течение нулевого часа.
3 3 5 4 4 0 1 3 3 2 3 1
1 3
4 5 4 2 1 0 3 4 3 3 2 1 2 1 4 1 3
4 1 2 3 4
Пытаясь спастись от мира спортивного программирования, Алина сбежала на вокзал и уехала прочь на ночной электричке. Минуты медленно уплывали в даль, и уставшую девочку клонило в сон. Ей снился город-сказка, где не надо программировать, а можно гулять, мечтать и наслаждаться жизнью. Внезапно дождь из интерактивных задач разрушил эту идиллию.
Проснувшись и открыв окно, Алина задалась вопросом весьма философского свойства: «Где я?». С перрона потерявшейся девочке сообщили, что этот город, не похожий ни на что вокруг, представляет собой неориентированный граф на \(n\) вершинах и \(m\) ребрах. Сeй невероятный факт, однако, нисколько не удивил Алину. Она давно мечтала побывать в одном таком городе — Петербурге. Его уникальной отличительной особенностью является то, что хотя бы половина его ребер — мосты (определение дано в конце условия). Так как никакие другие города Алине не интересны, она решила ограничиться расспросом находящихся на платформе эрудированных путешественников. Любой из их них может по данной вершине \(v\) сообщить любое ещё не названное ребро, исходящее из нее, или же заявить об отсутствии таковых.
Алина неуверена в своих силах, поэтому попросила вас помочь ей определить, попала ли она в Петербург. Так как её поезд скоро продолжит свой путь, задать больше \(3n\) вопросов не получится.
Обратите внимание, что в графе могут присутствовать петли и кратные ребра.
В первой строке стандартного потока ввода даны два целых числа \(n\) и \(m\) (\(1 \le n, m \le 100\,000\)) — число вершин и ребер в графе соответственно.
Для того, чтобы узнать очередное ребро, исходящее из \(u\)-й вершины (\(1 \le u \le n\)), нужно вывести « ? \(u\) ». После этого ваша программа на вход получит целое число \(v\) (\(-2 \le v \le -1\) или \(1 \le v \le n\)) — \(v = a + b - u\), если существует ребро \(ab\), которое инцидентно вершине \(u\) и ещё не было названо , \(-1\), если такого ребра не существует и \(-2\), если вы превысили допустимое число запросов. В последнем случае ваша программа должна немедленно завершиться, в ином случае жюри не гарантирует корректность полученного вами вердикта.
Вам разрешается задать не более \(3n\) вопросов.
Чтобы сообщить, что ответ найден, требуется вывести « ! Yes » или « ! No », в зависимости от того, является ли загаданный граф Петербургом. В случае положительного ответа выведите \(\lceil\frac{m}{2}\rceil\) строк, по два целых числа \(u_i\) и \(v_i\) в каждой (\(1 \le u_i, v_i \le n\)), обозначающих, что ребро \((u_i, v_i)\) является мостом. Любое ребро в приведенном списке должно встречаться не более одного раза (кратные ребра считаются различными).
Запрос на вывод ответа не входит в ограничение на \(3n\) запросов.
Не забывайте сбрасывать буфер после каждого запроса. Например, на языке C++ надо использовать функцию fflush(stdout) или вызов cout.flush() , на Java вызов System.out.flush() , на Pascal flush(output) и stdout.flush() для языка Python.
Подзадача 0. Тесты из условия
Подзадача 1. (27 баллов) \(N, M \leq 10\). Пройдена подзадача 0.
Подзадача 2. (30 баллов) \(N \leq 10000, M \leq 20000\). Пройдена подзадача 1.
Подзадача 3. (1 балл за каждый пройденный тест) Нет дополнительных ограничений. Пройдена подзадача 2.
В условии в примере взаимодействия вводимые и выводимые данные расположены для удобства восприятия в хронологическом порядке, при реальном взаимодействии никакие «лишние» переводы строк возникать не должны.
Ввод-вывод в примерах демонстрирует пример взаимодействия вашей программы с проверяющей системой.
В первом примере был загадан граф на трех вершинах с ребрами \((1, 2)\), \((2, 3)\) и \((3, 1)\).
Во втором примере была загадан граф на четырех вершинах с ребрами \((1, 2)\), \((2, 3)\), \((3, 4)\) и \((2, 3)\).
Ребро, соединяющее вершины \(u\) и \(v\), называется мостом, если после его удаления между вершинами \(u\) и \(v\) не существует пути.
3 3 2 2 -1 3 -1 -1
? 3 ? 1 ? 2 ? 1 ? 1 ? 3 ! No
4 4 2 3 2 -1 4 -1 -1 -1
? 1 ? 2 ? 3 ? 1 ? 3 ? 3 ? 2 ? 4 ! Yes 1 2 3 4
Задан ориентированный ациклический граф с \(n\) вершинами и \(m\) ребрами. Также задана перестановка вершин графа. Необходимо проверить, является ли данная перестановка топологической сортировкой.
В первой строке даны два числа \(n\) и \(m\) — количество вершин и ребер в графе соответственно (\(1 \leq n, m \leq 10^5\)). В следующих \(m\) строках заданы пары чисел \(u_i, v_i\), означающие, что в графе есть ребро из вершины \(u_i\) в вершину \(v_i\). В последней строке задана перестановка из \(n\) элементов.
Выведите "YES" (без кавычек), если данная перестановка является топологической сортировкой и "NO" в противном случае.
3 3 2 3 1 3 1 2 2 1 3
NO
3 3 3 2 1 2 3 1 3 1 2
YES
У Аркадия в саду есть одна необычная яблоня, с которой иногда необходимо собирать яблоки. Так как яблоня необычная, на ней есть \(n\) соцветий, они пронумерованы от 1 до \(n\). Соцветие номер 1 находится около корня дерева, любое другое соцветие с номером \(i(i>1)\) расположено на верхнем конце ветки, нижний конец которой расположен в соцветии \(p_i\).
Когда яблоки созревают, одновременно появляется ровно по одному яблоку в каждом соцветии. В тот же момент все яблоки начинают скатываться вниз по веткам к корню дерева. Каждую секунду все яблоки, кроме находящегося в первом соцветии, одновременно скатываются на одну ветку ближе к корню, то есть, например, из соцветия a яблоко попадет в соцветие \(p_a\). Яблоки, находившиеся в первом соцветии, забирает Аркадий. Яблоня необычная, поэтому, если в какой-то момент в одном соцветии оказываются два яблока, они аннигилируют. Так происходит с каждой парой, например, если в соцветие попадет одновременно 5 яблок, то останется только одно яблоко, а если в соцветие попадет одновременно 8 яблок, то не останется ни одного яблока. Таким образом, в каждом соцветии в любой момент времени находится не более одного яблока.
Помогите Аркадию, подсчитайте, сколько яблок он сможет забрать из первого соцветия за один урожай.
В первой строке следует целое число \(n(2 \le n \le 100000)\) — количество соцветий.
Во второй строке следует последовательность целых чисел \(p_2, p_3, ..., p_n\), состоящая из \(n−1\) числа, где \(p_i\) равно номеру соцветия, в которое скатывается яблоко из соцветия \(i\).
Выведите количество яблок, которые Аркадий сможет забрать из первого соцветия за один урожай.
3 1 2
3
5 4 2 5 1
5