В некотором государстве различные официальные вопросы решаются с помощью мощного бюрократического аппарата.
Программист Василий хочет получить разрешение на открытие своей фирмы, но он еще не знает с какими сложностями
ему придется столкнуться! Для того, чтобы оформить разрешение на свою деятельность Василий должен получить
определенный набор справок, каждую из которых выдает специально предназначенный для этого чиновник.
Задача усложняется тем, что многие из этих госслужащих не дают свои справки просто так. А именно, для
каждого из них известно, справки от каких других чиновников нужно иметь при себе, чтобы получить справку от этого.
Чтобы помочь Василию, напишите программу, которая выдаст последовательность посещения чиновников, которая бы
гарантировала, что никто из них ему не откажет.
Будем считать, что чиновники занумерованы целыми числами от 1 до N. Тот факт, что для посещения чиновника
с некоторым номером, требуется справка от чиновника с другим номером, будем называть "условием".
Формат входного файла
Входной файл содержит числа N и M - количество чиновников и "условий" соответственно.
Далее следуют M пар целых чисел (ai, bi), каждая из которых обозначает, что для посещения чиновника с
номером bi нужно иметь справку от чиновника с номером ai. Пар, состоящих из двух одинаковых чисел, нет.
Формат выходного файла
Выведите в выходной файл N целых чисел - одну из возможных последовательностей посещения чиновников.
Если такой последовательности не существует (бывает же и такое!), выведите −1.
You are to write a program that receives a connected undirected graph and finds
all its articulation points, which are the vertices that, if removed,
leave disconnected graph.
Input file format
Input file contains two integers N and M.
Vertices are numbered with integer numbers from 1 to N.
M is the number of edges.
Each of next M lines contain pair of integers — numbers of vertices
connected by an edge. There are no pairs of equal numbers.
Output file format
Output file must contain integer representing a quantity of articulation
points, followed by numbers of corresponding vertices in arbitrary order.
Центральная предметно-методическая комиссия по информатике
Ограничение времени:
2 сек
Входной файл:
details.in
Ограничение памяти:
256 Мб
Выходной файл:
details.out
Условие
Предприятие «Авто-2010» выпускает двигатели для известных
во всем мире автомобилей. Двигатель состоит ровно из n деталей,
пронумерованных от 1 до n, при этом деталь с номером i
изготавливается за pi секунд.
Специфика предприятия «Авто-2010» заключается в том,
что там одновременно может изготавливаться лишь одна деталь двигателя.
Для производства некоторых деталей необходимо иметь предварительно
изготовленный набор других деталей.
Генеральный директор «Авто-2010» поставил перед предприятием
амбициозную задачу — за наименьшее время изготовить деталь с номером 1,
чтобы представить ее на выставке.
Требуется написать программу, которая по заданным зависимостям порядка
производства между деталями найдет наименьшее время,
за которое можно произвести деталь с номером 1.
Система оценивания
Решения, правильно работающие только для тестов, в которых n не превосходит 10,
будут оцениваться из 40 баллов.
Решения, правильно работающие только для тестов, в которых n не превосходит 100,
будут оцениваться из 60 баллов.
Решения, правильно работающие только для тестов, в которых n не превосходит 1000,
будут оцениваться из 80 баллов.
Формат входного файла
Первая строка входного файла содержит число n — количество деталей двигателя.
Вторая строка содержит n натуральных чисел p1, p2… pn,
определяющих время изготовления каждой детали в секундах.
Каждая из последующих n строк входного файла описывает характеристики
производства деталей. Здесь i-ая строка содержит число деталей ki,
которые требуются для производства детали с номером i, а также их номера.
Известно, что не существует циклических зависимостей в производстве деталей.
Формат выходного файла
В первой строке выходного файла должны содержаться два числа:
минимальное время (в секундах), необходимое для скорейшего производства
детали с номером 1 и число k деталей, которые необходимо для этого произвести.
Во второй строке требуется вывести через пробел k чисел — номера деталей
в том порядке, в котором следует их производить
для скорейшего производства детали с номером 1.
Дан ориентированный граф. Подсчитайте, сколько пар вершин (i,j) имеют
общего предка. Общим предком вершин i и j называется такая вершину k,
что и i, и j достижимы из k.
Формат входного файла
В первой строке входного файла содержатся целые числа — количество вершин и рёбер в графе.
Далее следуют M строк по два числа от 1 до N.
Пара чисел (a,b) означает, что из вершины a есть ребро в вершину b.
Вам задан связный ориентированный граф с N вершинами и M ребрами.
Найдите компоненты сильной связности заданного графа и топологически отсортируйте его конденсацию.
Формат входного файла
Граф задан во входном файле следующим образом: первая строка содержит числа N и M.
Каждая из следующих M строк содержат описание ребра - два целых числа из диапазона от 1 до
N - номера начала и конца ребра.
Формат выходного файла
На первой строке выведите число K - количество компонент сильной связности в заданном графе.
На следующей строке выведите N чисел - для каждой вершины выведите номер компоненты сильной связности,
которой принадлежит эта вершина. Компоненты сильной связности должны быть занумерованы таким образом,
чтобы для любого ребра номер компоненты сильной связности его начала не превышал номера компоненты
сильной связности его конца.
Центральная предметно-методическая комиссия по информатике
Ограничение времени:
1 сек
Входной файл:
transform.in
Ограничение памяти:
256 Мб
Выходной файл:
transform.out
Условие
В некотором королевстве есть n городов, соединенных магическими порталами.
Каждая пара различных городов соединена ровно одним магическим порталом,
позволяющим мгновенно перемещаться из одного города в другой.
Из-за свойств магии, определяющей работу порталов, каждый портал можно использовать
только в одну сторону. Для каждой пары городов A и B известно, можно ли воспользоваться
порталом для перемещения напрямую из A в B или из B в A.
Из-за особенностей магических порталов иногда при перемещении жителей королевства
из одного города в другой приходится использовать несколько порталов.
Также могут существовать такие пары городов, что из одного города в другой нельзя добраться,
используя только магические порталы.
Жители королевства называют город совершенным, если из него можно добраться
до любого другого города в королевстве, используя только магические порталы.
Пусть изначально количество совершенных городов в королевстве равно k.
Недавно король принял решение выбрать пару городов и изменить разрешенное направление
перемещения по порталу, соединяющему их, на противоположное.
Для выбора лучшего варианта король хочет понять, какое количество совершенных городов
может оказаться в королевстве после перенастройки ровно одного портала.
Для получения этой информации король планирует запросить в министерстве транспорта
соответствующий отчет.
Король может запросить либо частичный, либо полный отчет.
Содержимое отчета зависит от параметра L, для частичного отчета L = k + 1,
для полного отчета L = 1.
Отчет содержит для каждого целого числа m, такого что m ≥ L, число таких пар городов A и B,
для которых выполняются следующие условия:
исходно магический портал позволяет перемещаться напрямую из города A в город B;
если изменить направление перемещения этого магического портала на противоположное,
чтобы он позволял напрямую перемещаться из города B в город A,
то количество совершенных городов в королевстве станет равным m.
Таким образом, частичный отчет содержит информацию только о тех способах перенастройки
одного портала, которые строго увеличивают количество совершенных городов в королевстве.
Полный отчет содержит информацию обо всех способах перенастройки одного портала.
Требуется написать программу, которая по информации о разрешенных направлениях перемещения
с использованием магических порталов, и информации о том, требуется предоставить частичный
или полный отчет, формирует соответствующий отчет и выводит его в описанном ниже формате.
Пояснения к примерам
В приведенных примерах изначально совершенным является только город 2.
Изменив направление порталов, соединяющих пары городов (2, 3), (2, 4) или (2, 5),
можно сделать все города совершенными. Изменение направление любого другого портала
делает совершенным один город.
Внимание! Второй тест не подходит под ограничения для первых трех подзадач,
но решение принимается на проверку только в том случае, если оно выводит правильный ответ
на все тесты из примера. Решение должно выводить правильный ответ на второй тест даже,
если оно рассчитано на решение только каких-либо подзадач из первых трех.
В других тестах n ≠ 5.
Система оценивания и описание подзадач
В этой задаче четыре подзадачи. Баллы за каждую подзадачу начисляются только в случае,
если все тесты подзадачи пройдены.
Подзадача 1 (20 баллов)
2 ≤ n ≤ 50, p = 0
Подзадача 2 (30 баллов)
2 ≤ n ≤ 300, p = 0
Подзадача 3 (20 баллов)
2 ≤ n ≤ 2000, p = 0
Подзадача 4 (30 баллов)
2 ≤ n ≤ 2000, p = 1
Получение информации о результатах окончательной проверки
По запросу сообщается баллы за каждую подзадачу.
Формат входного файла
Первая строка входного файла содержит два целых числа:
n — количество городов в королевстве
и p, равное либо 0, если требуется вывести частичный отчет,
либо 1, если требуется вывести полный отчет.
Последующие n строк содержат по n символов, каждый из которых может быть
«+», «–» или «.», и i-я из этих строк описывает магические порталы,
соединяющие i-й город с другими городами.
В i-й строке j-й символ равен «+», если магический портал позволяет
напрямую перемещаться из i-го города в j-й, равен «–», если магический портал
позволяет напрямую перемещаться из j-го города в i-й, и равен «.», если i = j.
Формат выходного файла
Первая строка выходного файла должна содержать одно целое число k —
количество совершенных городов в королевстве.
Если требуется частичный отчет (p = 0), то вторая строка выходного файла
должна содержать (n−k) целых неотрицательных чисел, разделенных пробелами,
где i-е из этих чисел должно быть равно количеству пар городов, изменение направления
портала между которыми на противоположное приводит к тому, что количество
совершенных городов в королевстве станет равным (k + i). Если при этом k = n,
то вторая строка может отсутствовать, либо быть пустой.
Если требуется полный отчет (p = 1), то вторая строка должна содержать
n целых неотрицательных чисел, разделенных пробелами,
где i-е из этих чисел должно быть равно количеству пар городов,
изменение направления портала между которыми на противоположное приводит к тому,
что количество совершенных городов в королевстве станет равным i.
Телекоммуникационная сеть крупной IT-компании содержит n серверов,
пронумерованных от 1 до n. Некоторые пары серверов соединены двусторонними каналами
связи, всего в сети m каналов. Гарантируется, что сеть серверов устроена таким образом, что
по каналам связи можно передавать данные с любого сервера на любой другой сервер,
возможно с использованием одного или нескольких промежуточных серверов.
Множество серверов A называется отказоустойчивым, если при недоступности
любого канала связи выполнено следующее условие. Для любого не входящего в это
множество сервера X существует способ передать данные по остальным каналам на сервер X
хотя бы от одного сервера из множества A.
На рис. 1 показан пример сети и отказоустойчивого множества из серверов с
номерами 1 и 4. Данные на сервер 2 можно передать следующим образом. При
недоступности канала между серверами 1 и 2 — с сервера 4, при недоступности канала
между серверами 2 и 3 — с сервера 1. На серверы 3 и 5 при недоступности любого канала
связи можно по другим каналам передать данные с сервера 4.
Рис. 1. Пример сети и отказоустойчивого множества серверов.
В рамках проекта группе разработчиков компании необходимо разместить свои
данные в сети. Для повышения доступности данных и устойчивости к авариям разработчики
хотят продублировать свои данные, разместив их одновременно на нескольких серверах,
образующих отказоустойчивое множество.
Чтобы минимизировать издержки, необходимо выбрать минимальное по количеству серверов отказоустойчивое множество. Кроме того, чтобы узнать, насколько гибко устроена сеть, необходимо подсчитать количество способов
выбора такого множества, и поскольку это количество способов может быть большим,
необходимо найти остаток от деления этого количества способов на число 109 + 7.
Требуется написать программу, которая по заданному описанию сети определяет
следующие числа: k — минимальное количество серверов в отказоустойчивом множестве
серверов, c — остаток от деления количества способов выбора отказоустойчивого множества
из k серверов на число 109 + 7
Формат входного файла
Первая строка входного файла содержит целые числа n и m — количество серверов и
количество каналов связи соответственно.
Следующие m строк содержат по два целых числа и описывают каналы связи между
серверами. Каждый канал связи задается двумя целыми числами: номерами серверов,
которые он соединяет.
Гарантируется, что любые два сервера соединены напрямую не более чем одним
каналом связи, никакой канал не соединяет сервер сам с собой, и для любой пары серверов
существует способ передачи данных с одного из них на другой, возможно с использованием
одного или нескольких промежуточных серверов.
Формат выходного файла
Выведите два целых числа, разделенных пробелом: k — минимальное число серверов
в отказоустойчивом множестве серверов, c — количество способов выбора
отказоустойчивого множества из k серверов, взятое по модулю 109 + 7
Ограничения
2 ≤ n ≤ 200000, 1 ≤ m ≤ 200000
Система оценки и описание подзадач
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой
подзадачи и необходимых подзадач успешно пройдены.
Подзадача
Баллы
Дополнительные ограничения
Необходимые подзадачи
n
m
1
25
2 ≤ n ≤ 10
1 ≤ m ≤ 45
2
27
2 ≤ n ≤ 200000
m = n − 1
3
28
2 ≤ n ≤ 1000
1 ≤ m ≤ 5000
1
4
21
2 ≤ n ≤ 200000
1 ≤ m ≤ 200000
1, 2, 3
Описание подзадач и системы оценивания
По запросу сообщается результат окончательной проверки на каждом тесте.
Пояснение к примеру
В приведённом примере отказоустойчивыми являются следующие множества из двух серверов:
{1, 3}, {1, 4}, {1, 5}.
Дано дерево из N вешрин, все некоторым образом пронумерованы, а корень имеет номер 1.
Найдите LCA для некоторых пар вершин.
Формат входного файла
Первая строка входного файла состоит из единственного числа N. Далее в N−1 строке следует описание дерева:
пары соединенных вершин. После этого до конца файла записаны пары номеров веришин, для которых следует найти LCA.
Количество этих пар не превосходит 10^5.
Формат выходного файла
В выходном файле для каждого запроса выведите единственное число: номер LCA.
You are to write a program that receives an undirected connected graph and finds its Eulerian cycle.
Input file format
Input file contains two integers N, M.
Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of following M lines contains a pair of
vertex numbers, connected by some edge. There is at most one edge connecting two vertices.
Output file format
Output file must contain a sequence of vertex numbers in order of traversal in an Eiler cycle.
If there does not exist any Eiler cycle, output file must contain −1.
