Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах --> Эйлеров цикл
---> 3 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: 1 Отображать по:
#3201
Студентам --- бесплатно!
  

Зал Большого галактического театра состоит из \(S\) рядов, по \(S\) мест в каждом ряду.Продажа билетов на каждый спектакль происходит по следующему принципу: первые \(S^2 - N\) ценителей прекрасного приобретают билеты на любые места по их вкусу, а оставшиеся \(N\) кресел администрация бесплатно выделяет студентам, отдавая дань сложившимся традициям.

Во избежание обвинений в дискриминации по половому признаку, рассаживать студентов по этим \(N\) местам необходимо таким образом, чтобы:

  • в каждом ряду количество девушек-студенток и количество юношей-студентов различалось бы не более чем на 1;
  • на каждой "вертикали мест" (т. е. местах, имеющих один и тот же номер, но расположенных в разных рядах) количество девушек-студенток и количество юношей-студентов также различалось бы не более чем на 1.
Таким образом, после продажи билетов ценителям прекрасного билетёры должны распределить оставшиеся \(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\)-го места в той же нумерации, в которой они были перечислены во входных данных.

Примечания

Тесты состоят из четырёх групп.

  1. Тесты 1 и 2. Тесты из условия, оцениваются в 0 баллов.
  2. Тесты 3--19. В них \(S \le 1\,000\), \(N \le 30\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  3. Тесты 20--30. В них \(S \le 1\,000\), \(N \le 1\,000\). Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  4. Тесты 31--34. Off-line группа, полные ограничения. Каждый тест оценивается в 10 баллов (тесты оцениваются независимо друг от друга). При этом баллы за тесты этой группы ставятся только тогда, когда программа проходит все тесты групп 1 и 2. Если программа не проходит хотя бы один из тестов групп 1 и 2, то баллы за тесты группы 3 не ставятся.

Примеры
Входные данные
2 2
2 1
1 2
Выходные данные
MW
Входные данные
3 5
1 2
2 3
1 3
2 1
1 1
Выходные данные
WMWWM
#3891
Совершенно секретно
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

В секретном 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
#111988
Хоровод
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Настал декабрь, и вместе с ним пришло время готовиться к Новому Году. На острове рыцарей и лжецов этот праздник традиционно отмечается очень масштабно. Праздничный стол, новогодняя ёлка, конфетти и бенгальские огни — все готово к началу торжества.

Как вы знаете, на острове рыцарей и лжецов живут только два вида жителей — рыцари и лжецы. Рыцари никогда не лгут, так как этого им не позволяют их высокие моральные принципы. Лжецы же, наоборот, всегда говорят только неправду.

Важнейшей частью празднования Нового года является хоровод вокруг елки. Все приглашенные жители острова берутся за руки и движутся по кругу под музыку. Поскольку население острова весьма консервативно, то в этом году жители хотят выстроиться в круг в том же порядке, что и в прошлом. Однако данных о том, как был устроен хоровод, не сохранилось. Известно только, что каждый житель острова запомнил, кем были его соседи по хороводу (рыцарями или лжецами).

Опросив каждого человека, приглашенного на празднование, вы узнали, кем были их соседи по их словам (при этом лжецы говорят неправду про каждого соседа). Осталось только придумать какое-нибудь расположение жителей острова в круг так, чтобы их показания не противоречили друг другу.

Напишите программу, которая по списку жителей и их показаний определит, существует ли такое расположение или же выстроиться в хоровод как в прошлом году не получится.

Входные данные

В первой строке входных данных дано целое число 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

Примечание

Тесты к этой задаче состоят из четырёх групп.

  • Тесты 1 – 2. Тесты из условия, оцениваются в ноль баллов.
  • Тесты 3 – 10. На тесты этой группы накладывается ограничение n ≤ 10. Группа тестов оценивается в 20 баллов, баллы ставятся только при прохождении всех тестов группы.
  • Тесты 11 – 26. На тесты этой группы накладывается ограничение n ≤ 20. Группа тестов оценивается в 25 баллов, баллы ставятся только при прохождении всех тестов группы.
  • Тесты 27 – 38. В тестах этой группы дополнительные ограничения отсутствуют. Группа оценивается в 55 баллов, баллы ставятся только при прохождении всех тестов группы.

В первом примере, можно выстроить жителей в порядке (2, 1, 3, 5, 4) по часовой стрелке. Показания всех людей будут сходиться в этом случае, например, когда четвертый житель будет рыцарем, а все остальные четыре человека — лжецами.

Во втором примере, очевидно, нельзя получить никакого решения, так как выстроить двух человек в хоровод можно лишь одним способом. Рассмотрим два случая: если первый человек — рыцарь, то, по его словам, второй человек — лжец, однако, из лживости его слов следует, что первый человек не рыцарь. С другой стороны, если первый человек — лжец, то из его показаний следует, что второй человек — рыцарь, но второй человек говорит, что первый — тоже рыцарь. Таким образом, поскольку в обоих случаях мы получили противоречие, не существует способа построить хоровод из имеющегося набора жителей.

Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест