--->
9 задач
<---
Источники
В городе есть N площадей, соединенных улицами. При этом количество улиц не превышает 100000 и существует не более трех площадей, на которые выходит нечетное количество улиц. Для каждой улицы известна ее длина. По каждой улице разрешено движение в обе стороны. В городе есть хотя бы одна улица. От каждой площади до любой другой можно дойти по улицам.
Почтальону требуется пройти хотя бы один раз по каждой улице. Почтальон хочет, чтобы длина его пути была минимальна. Он может начать движение на любой площади и закончить также на любой (в том числе и на начальной).
Помогите почтальону составить такой маршрут.
Сначала записано число N — количество площадей в городе (2≤N≤1000). Далее следуют N строк, задающих улицы. В i-ой из этих строк находится число mi — количество улиц, выходящих из площади i. Далее следуют \(m_i\) пар натуральных чисел: в j-ой паре первое число — номер площади, в которую идет j-ая улица с \(i\)-ой площади, а второе число — длина этой улицы.
Между двумя площадями может быть несколько улиц, но не может быть улицы с площади на нее саму.
Все числа во входном файле не превосходят 100000
Если решение существует, то в первую строку выходного файла выведите одно число — количество улиц в искомом маршруте, а во вторую — номера площадей в порядке их посещения.
Если решения нет, выведите в выходной файл одно число –1.
Если решений несколько, выведите любое.
4 2 2 1 2 2 4 1 2 4 4 3 5 1 1 2 2 5 4 8 2 3 8 2 4
5 1 2 3 4 2 1
Для решения транспортной проблемы в некотором городе до недавнего времени использовались N
(N≤100000) автобусных маршрутов. Каждый маршрут начинался на одной из M (M≤100000) площадей и
там же заканчивался. В процессе проезда по маршруту автобус мог несколько раз проезжать одну и ту же площадь, и даже мог проезжать более одного раза по одной и той же улице в одном и том же направлении.
В определенный момент местные власти решили сократить количество автобусных маршрутов в
городе до одного. По их мнению, должен был остаться лишь один маршрут, который проходил бы по всем
улицам, по которым раньше проходили автобусные маршруты, причем в том же направлении (но не
обязательно в том же порядке). Если по каким-либо улицам автобусы ездили в обоих направлениях, то и
новый маршрут должен проходить по этим улицам в обоих направлениях. По тем улицам и в тех
направлениях, по которым раньше автобусы не ездили, новый маршрут проходить не должен. Однако так
как контролеров увольнять нельзя, власти решили, что по каждой улице в каждом направлении новый
маршрут должен проходить столько раз, сколько по ней проходили все старые маршруты, вместе взятые.
Требуется написать программу, которая для заданных исходных данных определяет требуемый
местным властям автобусный маршрут.
Входной файл состоит из следующей последовательности строк. Первая строка содержит число N – количество автобусных маршрутов, M – количество площадей. Каждая из последующих N строк служит для описания соответствующего автобусного маршрута и содержит сначала число k (k≤100000), определяющее количество элементов маршрута, а затем k+1 чисел, задающих номера площадей, которые последовательно проезжает автобус на этом маршруте. Общая длина маршрутов не более 100000 улиц. При описании маршрута всегда задаются номера первой и последней площади маршрута, причем они всегда совпадают.
Выходной файл должен содержать либо описание нового маршрута в том же формате, что используется во входном файле, либо одно число 0, если организовать требуемый маршрут не удастся.
2 5 6 1 2 3 4 3 2 1 2 4 5 4
9 1 2 3 4 5 4 3 2 1
В королевстве \(N\); городов, пронумерованных от 1 до \(N\). Столица имеет номер 1. Каждый город окружен городской стеной с 4 воротами. Ворота пронумерованы следующим образом: ворота \(i\)-го города (1 \(\le\) \(i\) \(\le\) \(N\)) имеют номера 4\(i\)−3, 4\(i\)−2, 4\(i\)−1, 4\(i\). Через каждые ворота проходит ровно 1 дорога, которая ведет до некоторых ворот другого города (заметьте, что может существовать несколько дорог между двумя городами). По всем дорогам можно двигаться в обоих направлениях. Благодаря системе туннелей и мостов дороги не пересекаются вне городов.
Королевский гонец должен развесить копии Очень важного Королевского Указа на внешней стороне всех ворот каждого города. Гонец может свободно передвигаться от одних ворот к другим в пределах города, но вне города он может двигаться только по дорогам. Гонец выезжает из столицы и должен туда вернуться после выполнения задания.
Может ли гонец выполнить поручение, проходя через каждые ворота только один раз? Выход из города через ворота только для того, чтобы вывесить на их внешней стороне указ, а затем немедленное возвращение в город, считается за один проход через ворота.
Первая строка входного файла содержит целое число \(N\) (2 \(\le\) \(N\) \(\le\) 1000). Каждая из последующих 2\(N\) строк описывает одну дорогу и содержит 2 целых числа, разделенных пробелом: номера ворот, соединенных дорогой.
В первую строку выходного файла выведите Yes или No в зависимости от того, может ли поручение гонца быть выполнено, если проходить через ворота только один раз. В случае если это возможно, вторая строка выходного файла должна содержать 4\(N\) целых чисел, разделенных пробелом: номера ворот в порядке прохождения через них гонцом. Если существует несколько решений, выведите любое из них.
Всем известно, что в позапрошлом веке ковбои занимались перегоном скота. Перегон скота всегда считался опасным делом. Ковбой Джон, готовясь к очередному перегону, изучал план местности. Так как местность гористая, то добраться из одного поселения в другое можно только по дорогам, возможно через другие поселения. Главной опасностью на пути были бандиты, проживающие в разных населенных пунктах, и организующие группировки для нападения на ковбоев. Чтобы их разобщить, Джон разработал гениальный план полной изоляции поселений друг от друга.
Посоветовавшись с напарниками, Джон пришел к выводу, что временно дороги можно вывести из строя, устроив камнепад. Под покровом ночи можно выехать из одного населения в другое, остановиться где-то посреди дороги и устроить камнепад так, чтобы по этой дороге нельзя больше проехать никому. Камни падают позади повозки, поэтому обратной дороги нет. Но зато можно ехать в другой населенный пункт, и если из него существуют дороги, то и их можно вывести из строя.
Сам Джон этого сделать не может, только он знает тайные тропы и должен перегонять стадо. Поэтому он решил использовать наемников. Наемники есть в любом поселении и в любом количестве, однако, за каждого из них приходится платить немалую сумму, поэтому Джон хочет потратить как можно меньше денег. Помогите Джону определить минимальное число наемников, которые смогут привести в непригодность абсолютно все дороги и изолировать все поселения.
В первой строке каждого теста находятся два целых неотрицательных числа N (0 < N < 1000) – количество поселений и M (0 ≤ M ≤ 100 000) – количество дорог, их соединяющих. Далее следует M строк, содержащих описание дорог. В i-й строке находятся два натуральных числа V и U (1 ≤ V, U ≤ N) – номера поселений, которые соединяет i-я дорога. Между двумя различными поселениями существует не более одной дороги, но может существовать несколько маршрутов. Нет дорог, которые образуют петлю, исходящую из поселения и ведущую в него же, не заходя в другие поселения. Не гарантируется, что существует маршрут между любой парой поселений. Маршрутом называется такая последовательность поселений s1-s2- … -sn, что любые два последовательных поселения si и si+1 соединены дорогой..
Выведите минимальное количество наемников, необходимое для изоляции всех поселений.
6 6 1 2 2 3 1 3 4 5 5 6 4 6
2
Зал Большого галактического театра состоит из \(S\) рядов, по \(S\) мест в каждом ряду.Продажа билетов на каждый спектакль происходит по следующему принципу: первые \(S^2 - N\) ценителей прекрасного приобретают билеты на любые места по их вкусу, а оставшиеся \(N\) кресел администрация бесплатно выделяет студентам, отдавая дань сложившимся традициям.
Во избежание обвинений в дискриминации по половому признаку, рассаживать студентов по этим \(N\) местам необходимо таким образом, чтобы:
Каждое место в зале определяется двумя числами от 1 до \(S\) - номером ряда и номером самого места в этом ряду. Студенческое кресло номер \(i\) расположено в \(a_i\)-м ряду и имеет в нём номер \(b_i\). Поскольку ценители прекрасного могли занять совершенно любые места, числа \(a_i\) и \(b_i\) могут принимать любые значения от 1 до \(S\). В частности, может оказаться так, что в каком-нибудь ряду не будет ни одного студенческого места.
Ради упрощения работы билетёров администрация обращается к вам с заданием написать программу, которая автоматизирует процесс распределения студенческих мест на мужские и женские.
Сначала вводятся два целых числа \(S\) и \(N\) (\(1 \le S \le 100\,000\), \(1 \le N \le \min\{100\,000, S^2\}\)). Далее расположены \(N\) пар натуральных чисел \((a_i, b_i)\), не превосходящих \(S\). Гарантируется, что все места различные.
Если искомого способа не существует, выведите Impossible.Иначе выведите единственную строку из \(N\) символов ‘M’ (мужское) и ‘W’ (женское). Символ на \(i\)-й позиции соответствует статусу \(i\)-го места в той же нумерации, в которой они были перечислены во входных данных.
Тесты состоят из четырёх групп.
2 2 2 1 1 2
MW
3 5 1 2 2 3 1 3 2 1 1 1
WMWWM