Бойцовский клуб дебатов - необычный клуб во всех отношениях. Каждый из \(2^{n}\) его членов заполнил специальную анкету, содержащую \(n\) вопросов с бинарным ответом (да/нет) о своих взглядах. Ответы каждого человека могут быть представлены в виде последовательности из \(n\) бит, иначе говоря в виде числа от \(0\) до \(2^{n} - 1\).
Перечислим ещё несколько инетерсных фактов о бойцовском клубе дебатов.
В первой строке вводится число \(n\) (\(2 \le n \le 18\)) - количество вопросов в анкете.
В последующих \(2^{n - 1}\) строках даны пары людей. В \(i\) строке даны целые числа \(a_i\) и \(b_i\), разделённые одним пробелом - что означает, что люди, чьи анкеты закодированы числами \(a_i\) и \(b_i\) являются парой. Гарантируется, что каждое целое число от \(0\) до \(2^{n} - 1\) встретится во вводе ровно один раз.
Выведете строку со единственным словом 'NO' , если не существует рассадки членов клуба по местам удоволетворяющей условию.
Иначе, выведете в первой строке слово 'YES'. Во второй строке выведите \(2 ^ n\) чисел, разделённые пробелами, кодирующие ответы последовательных людей вокруг стола - корректную рассадку (стол круглый, поэтому можно начинать вывод с любого человека).
Если существует несколько решений, выведите любое.
В задаче оценка по подгруппам. Подгруппы отличаются значением \(n\). Для для \(n = 2\) - \(4\) балла за подгруппу, для каждого значения \(n\) от \(3\) до \(18\) по \(6\) баллов за подгруппу.
3 0 5 4 1 3 6 7 2
YES 0 5 7 2 6 3 1 4
В полутемной комнате Милан сел за стол и начал думать о возможных последствиях ядерной катастрофы в своем городе. Поскольку Милан - мэр города, он очень хорошо знаком с такими событиями.
А именно, он знает, что в его городе живет ровно \(N\) человек и каждый житель живет в своем собственном доме. Между \(M\) парами домов есть дороги, и для каждой дороги известно, сколько времени потребуется для ее прохождения. Наконец, Милан знает, в каких \(K\) домах есть атомные укрытия и сколько людей помещается в каждое укрытие. Учитывая все это, у Милана возникает следующий вопрос: «Сколько времени нужно, чтобы эвакуировать всех жителей города?»
Помогите Милану ответить на этот вопрос.
Конечно, эвакуация означает, что каждый житель попадает в какое-то атомное убежище. Можно предположить, что жители двигаются оптимально (по кратчайшему пути) и что несколько человек могут двигаться по одной дороге одновременно, возможно в разных направлениях. Также можно считать, что между любыми двумя домами есть хотя бы один путь, проходящий по дорогам.
Первая строка содержит натуральные числа N \((1 \le N \le 100000)\), \(M\) \((1 \le M \le 300000)\) и \(K\) \((1 \le K \le 17)\), которые обозначают количество жителей, количество дорог и количество атомных укрытий. Дома пронумерованы числами от \(1\) до \(N\).
В каждой из следующих \(M\) строк даны три натуральных числа \(A\), \(B\) \((1 \le A, B \le N, A \neq B)\) и \(C\) \((1 \le C \le 10^9)\), которые обозначают, что между домами с номерами \(A\) и \(B\) есть дорога, для прохождения которой требуется \(C\) единиц времени.
В каждой из следующих \(K\) строк даны два натуральных числа \(X\) \((1 \le X \le N)\) и \(Y\) \((1 \le Y \le 10^9)\), которые обозначают, что в доме с номером \(X\) есть атомное убежище, где может быть укрыто максимум \(Y\) людей.
Общая вместимость всех укрытий больше или равна \(N\).
В единственной строке выведите минимальное время, необходимое для эвакуации всех жителей города.
В задаче 3 подгруппы:
5 5 2 1 2 1 1 3 3 2 3 4 3 4 1 4 5 1 1 10 4 2
3
7 8 3 1 2 5 2 3 3 3 4 5 1 4 1 4 5 7 5 6 2 6 7 1 4 7 4 3 3 7 3 6 2
5