--->
9 задач
<---
Источники
В секретном 240 отделе ИПФ РАН \(N\) сотрудников и \(N\) компьютеров. В отделе вводятся новые требования к секретности. В соответствии с этими требованиями, для каждого сотрудника будут определены ровно \(K\) компьютеров, к которым этот сотрудник будет иметь допуск (т.е. за которыми этот сотрудник будет иметь право работать), причём так, что к каждому компьютеру будут иметь допуск ровно \(K\) сотрудников.
Информация о том, какой сотрудник к какому компьютеру будет иметь допуск, будет известна лишь непосредственно перед вступлением новых требований в силу. Таким образом, чтобы не прерывать работу отдела, сотрудники должны будут быстро решить, кто за каким компьютером будет работать. Для этого им необходимо заранее написать программу, которая по любому распределению допусков сотрудников найдёт рассадку сотрудников по компьютерам, удовлетворяющую этим допускам.
Обратите внимание, что значение \(K\) тоже будет известно лишь в последний момент. Из общих соображений секретности известно лишь, что \(K\) будет равняться или 1, или 2, или 4; поэтому ваша программа должна уметь работать для любого из этих трех значений \(K\).
В первой строке входного файла записаны натуральные числа \(N\) и \(K\) (\(1\leq N \leq 500\)). Далее следуют \(KN\) строк, в каждой из которых записаны два натуральных числа — номер сотрудника и номер компьютера, к которому этот сотрудник имеет допуск.
Гарантируется, что каждый сотрудник имеет допуск ровно к \(K\) компьютерам, что к каждому компьютеру ровно \(K\) сотрудников имеют допуск, и что \(K\) равно либо 1, либо 2, либо 4.
В выходной файл выведите \(N\) строк, в каждой по два числа — номер сотрудника и номер компьютера, за которым он должен работать. Строки можно выводить в произвольном порядке.
Если есть несколько решений, выведите любое. Можно доказать, что для любого входного файла, удовлетворяющего указанным ограничениям, всегда имеется как минимум одно решение.
3 1 2 3 3 1 1 2
3 1 1 2 2 3
2 2 1 2 2 1 2 2 1 1
1 2 2 1
Настал декабрь, и вместе с ним пришло время готовиться к Новому Году. На острове рыцарей и лжецов этот праздник традиционно отмечается очень масштабно. Праздничный стол, новогодняя ёлка, конфетти и бенгальские огни — все готово к началу торжества.
Как вы знаете, на острове рыцарей и лжецов живут только два вида жителей — рыцари и лжецы. Рыцари никогда не лгут, так как этого им не позволяют их высокие моральные принципы. Лжецы же, наоборот, всегда говорят только неправду.
Важнейшей частью празднования Нового года является хоровод вокруг елки. Все приглашенные жители острова берутся за руки и движутся по кругу под музыку. Поскольку население острова весьма консервативно, то в этом году жители хотят выстроиться в круг в том же порядке, что и в прошлом. Однако данных о том, как был устроен хоровод, не сохранилось. Известно только, что каждый житель острова запомнил, кем были его соседи по хороводу (рыцарями или лжецами).
Опросив каждого человека, приглашенного на празднование, вы узнали, кем были их соседи по их словам (при этом лжецы говорят неправду про каждого соседа). Осталось только придумать какое-нибудь расположение жителей острова в круг так, чтобы их показания не противоречили друг другу.
Напишите программу, которая по списку жителей и их показаний определит, существует ли такое расположение или же выстроиться в хоровод как в прошлом году не получится.
В первой строке входных данных дано целое число n (2 ≤ n ≤ 105) — количество жителей на острове лжецов.
В следующих n строках даны целые числа li и ri (0 ≤ li, ri ≤ 1) — данные о соседях i-го человека. Если li = 0, то i-й житель утверждает, что его сосед по хороводу в направлении против часовой стрелки был лжецом, а если li = 1, то рыцарем. Аналогично, число ri содержит информацию о соседе по часовой стрелке.
Требуется вывести «Yes», если существует способ выстроить людей по указанным правилам, или «No», если нет.
5
1 1
0 1
1 1
0 0
1 0
Yes
2
0 0
1 1
No
Тесты к этой задаче состоят из четырёх групп.
В первом примере, можно выстроить жителей в порядке (2, 1, 3, 5, 4) по часовой стрелке. Показания всех людей будут сходиться в этом случае, например, когда четвертый житель будет рыцарем, а все остальные четыре человека — лжецами.
Во втором примере, очевидно, нельзя получить никакого решения, так как выстроить двух человек в хоровод можно лишь одним способом. Рассмотрим два случая: если первый человек — рыцарь, то, по его словам, второй человек — лжец, однако, из лживости его слов следует, что первый человек не рыцарь. С другой стороны, если первый человек — лжец, то из его показаний следует, что второй человек — рыцарь, но второй человек говорит, что первый — тоже рыцарь. Таким образом, поскольку в обоих случаях мы получили противоречие, не существует способа построить хоровод из имеющегося набора жителей.
В секретном 240 отделе ИПФ РАН \(N\) сотрудников и \(N\) компьютеров. В отделе вводятся новые требования к секретности. В соответствии с этими требованиями, для каждого сотрудника будут определены ровно \(K\) компьютеров, к которым этот сотрудник будет иметь допуск (т.е. за которыми этот сотрудник будет иметь право работать), причём так, что к каждому компьютеру будут иметь допуск ровно \(K\) сотрудников.
Информация о том, какой сотрудник к какому компьютеру будет иметь допуск, будет известна лишь непосредственно перед вступлением новых требований в силу. Таким образом, чтобы не прерывать работу отдела, сотрудники должны будут быстро решить, кто за каким компьютером будет работать. Для этого им необходимо заранее написать программу, которая по любому распределению допусков сотрудников найдёт рассадку сотрудников по компьютерам, удовлетворяющую этим допускам.
Обратите внимание, что значение \(K\) тоже будет известно лишь в последний момент. Из общих соображений секретности известно лишь, что \(K\) будет равняться или 1, или 2, или 4; поэтому ваша программа должна уметь работать для любого из этих трех значений \(K\).
В первой строке входного файла записаны натуральные числа \(N\) и \(K\) (\(1\leq N \leq 100 000\)). Далее следуют \(KN\) строк, в каждой из которых записаны два натуральных числа — номер сотрудника и номер компьютера, к которому этот сотрудник имеет допуск.
Гарантируется, что каждый сотрудник имеет допуск ровно к \(K\) компьютерам, что к каждому компьютеру ровно \(K\) сотрудников имеют допуск, и что \(K\) равно либо 1, либо 2, либо 4.
В выходной файл выведите \(N\) строк, в каждой по два числа — номер сотрудника и номер компьютера, за которым он должен работать. Строки можно выводить в произвольном порядке.
Если есть несколько решений, выведите любое. Можно доказать, что для любого входного файла, удовлетворяющего указанным ограничениям, всегда имеется как минимум одно решение.
| Ввод | Вывод |
|---|---|
3 1 2 3 3 1 1 2 |
3 1 1 2 2 3 |
2 2 1 2 2 1 2 2 1 1 |
1 2 2 1 |
Бойцовский клуб дебатов - необычный клуб во всех отношениях. Каждый из \(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