На пригородной железной дороге N станций и M соединяющих их перегонов. Любые две станции соединены не более чем одним перегоном. Сеть перегонов устроена так, что, отправившись от любой станции, можно вернуться на нее, только проехав хотя бы один перегон дважды. На железной дороге организовано движение электричек. Каждая электричка ходит в обоих направлениях по своему маршруту между двумя конечными станциями и останавливается на всех промежуточных станциях
Для удобства пассажиров руководство железной дороги решило ввести новую систему оплаты проезда. По этой системе каждой станции присваивается некоторое целое число, называемое тарифным номером этой станции. Стоимость проезда между двумя станциями без пересадок определяется модулем разности тарифных номеров этих станций. Тарифные номера станций вдоль маршрута каждой электрички должны изменяться монотонно, то есть при движении в каком-либо направлении строго возрастать и, следовательно, строго убывать при движении в обратном направлении. Это обеспечивает рост стоимости проезда с увеличением количества пройденных перегонов.
Требуется написать программу, которая назначит каждой станции тарифный номер.
|
|
4 станции, 3 перегона: 1-4, 2-4, 3-4 Маршруты: 1-4-2, 2-4-3, 3-4-1. Ответ: решения нет |
|
|
5 станций, 4 перегона: 1-5, 2-5, 3-5, 4-5 Маршруты: 1-5-2, 2-5-3, 3-5-4, 4-5-1. Ответ: решение есть; например, следующее: номер станции: 1 2 3 4 5 тарифный номер: 1 4 1 5 3 Замечание: тарифные номера разных станций могут совпадать. |
В первой строке входных данных содержатся два целых числа: N — количество станций (2 ≤ N ≤ 100 000), и M — количество перегонов между ними (1 ≤ M ≤ N – 1). В последующих M строках записаны пары целых чисел a, b (a ≠ b, 1 ≤ a ≤ N, 1 ≤ b ≤ N), означающие наличие перегона между станциями a и b. За ними в отдельной строке записано единственное целое положительное число K — количество маршрутов электричек. В последующих K строках идут описания маршрутов электричек, по одному на строке. Каждое описание представляет собой последовательность целых чисел — номеров всех станций маршрута в порядке одного из двух возможных направлений следования электрички. Описание маршрута заканчивается числом 0.
Все номера станций в описании маршрута различны. Количество станций в каждом маршруте не менее двух. Любые две последовательные станции в маршруте каждой электрички соединены перегоном. Суммарное количество станций в описаниях всех маршрутов не превосходит 200 000. Могут быть станции и перегоны, через которые не проходит ни одна электричка.
В первую строку выведите «NO», если искомого назначения тарифных номеров не существует. В противном случае в первую строку выведите «YES», а в следующей строке — N целых положительных чисел, где i-е число — тарифный номер i-й станции. Тарифный номер каждой станции должен находиться в диапазоне от 1 до N.
Если существует несколько решений, необходимо вывести любое из них.
Тесты к этой задаче состоят из четырёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
6 5 1 2 5 2 5 6 4 5 3 2 6 1 2 0 5 6 0 3 2 1 0 5 2 3 0 4 5 2 0 6 5 4 0
YES 2 3 4 1 2 3
Для проведения олимпиады школьников по информатике требуется соединить компьютеры в сеть. Организаторы олимпиады разработали схему соединения компьютеров. В соответствии с этой схемой некоторые пары компьютеров должны быть соединены кабелем, и сигнал сможет дойти по кабелям от любого компьютера до любого другого, возможно, через другие компьютеры.
Некоторые компьютеры могут быть соединены циклически. Цикл называется простым, если каждый компьютер из этого цикла соединён ровно с двумя другими компьютерами этого цикла, и в этот цикл никакой кабель не входит более одного раза. Некоторые кабели могут не входить ни в какой цикл.
Известно, что в разработанной схеме никакой кабель не принадлежит двум простым циклам одновременно.
Организаторам олимпиады поручено разместить компьютеры в зале соревнований. При размещении должны выполняться следующие условия:
1.Компьютеры размещаются на плоскости в точках с целочисленными координатами.
2.Координаты компьютеров x и y лежат в диапазоне 0 ≤ x, y ≤ 106.
3.Никакие два компьютера не располагаются в одной точке.
4.Кабели являются отрезками прямых.
5.Кабели не пересекаются между собой и не проходят через точки размещения компьютеров, к которым они не подключены.
Требуется написать программу, выполняющую размещение компьютеров по заданному описанию схемы.
В первой строке входного файла содержатся числа N и M — количество компьютеров и количество кабелей в схеме (1 ≤ N ≤ 100 000, 0 ≤ M ≤ 200 000). В последующих M строках содержатся пары чисел, разделенных пробелами. Каждая такая пара описывает один кабель, числа представляют собой номера соединенных компьютеров. Компьютеры пронумерованы от 1 до N. Никакая пара не встречается дважды, и никакой кабель не соединяет компьютер с самим собой.
Выходной файл должен содержать N строк. Строка с номером i должна содержать координаты i-го компьютера, разделенные пробелом. Сначала выводится координата x, затем y. Разрешается вывести любой вариант размещения компьютеров, при котором выполняются условия 1–5.
Примечания
Решения, корректно работающие при отсутствии циклов, будут оцениваться из 40 баллов.
Решения, корректно работающие при наличии только одного цикла, будут оцениваться из 60 баллов.
Пример входных и выходных данных
|
Ввод |
Вывод |
|
13 14 11 12 11 13 1 3 3 5 5 8 8 9 8 6 6 3 4 6 4 2 6 10 10 11 10 7 7 4 |
1 0 3 0 1 1 3 1 0 2 2 2 4 2 1 3 1 4 3 3 3 4 2 5 4 5 |
Антивирусная IT-компания имеет официальную иерархическую структуру управления. В ней есть босс – единственный сотрудник, над которым нет начальника. Каждый из остальных сотрудников подчинён ровно одному сотруднику – своему начальнику. Начальник может иметь нескольких подчинённых и отдавать или передавать приказы любому из них. Приказы могут передаваться от одного сотрудника другому только по цепочке, каждый раз от начальника к его подчинённому. Сотрудник А главнее сотрудника Б в этой иерархии, если А может отдать или передать приказ сотруднику Б непосредственно, или через цепочку подчинённых. Босс главнее любого сотрудника. Оказалось, что все сотрудники объединены ещё в одну организованную подобным образом тайную иерархическую структуру, производящую компьютерные вирусы. В тайной структуре может быть другой босс, а у сотрудников – другие начальники. Будем называть пару сотрудников А и Б устойчивой, если А главнее Б и в основной, и в тайной иерархических структурах. Требуется написать программу, определяющую количество устойчивых пар в компании.
В первой строке задано число N – количество сотрудников компании (1 ≤ N ≤ 100 000). Во второй строке – N целых чисел ai, где ai = 0, если в официальной иерархии сотрудник с номером i является боссом, в противном случае ai равно номеру непосредственного начальника сотрудника номер i. В третьей строке – N целых чисел bi, где bi = 0, если в тайной иерархии сотрудник с номером i является боссом, в противном случае bi равно номеру непосредственного начальника сотрудника номер i. Нумерация сотрудников ведется с единицы в том порядке, в каком они упомянуты во входном файле.
Выходной файл должен содержать единственное число – количество устойчивых пар.
Данная задача содержит три подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.
3 0 3 1 0 1 1
2
5 2 0 1 3 4 3 1 0 2 4
7
После прохождения монеты по трубке ширина этой трубки уменьшается на 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 <= \(n\) <= 100
1 <= \(u_k\); \(w_k\) <= 300
Подзадача оценивается в 50 баллов.
1 <= \(n\) <= \(10^5\)
1 <= \(u_k\); \(w_k\) <= \(10^9\)
Подзадача оценивается в 50 баллов.
В первом примере первая монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 1, 3 и 4:
Вторая монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 2 и 6:
Третья монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 5 и 7:
7 2 1 3 2 0 0 6 3 4 1 5 1 0 0 0 0 7 2 0 0 0 0 0 0 0 0 0 0 5
3
4 0 0 2 1 4 1 3 1 0 0 0 0 0 0 0 0 3
-1
