images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
21/11/2024 19:59:31

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

1791. Студентам - бесплатно!

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Зал Большого галактического театра состоит из `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\ ≤\ S\ ≤\ 100\ 000`, `1\ ≤\ N\ ≤\ min(100\ 000,\ S^2)`). Далее расположены `N` пар натуральных чисел `(a_i;\ b_i)`, не превосходящих `S`. Гарантируется, что все места различные.
Если искомого способа не существует, выведите Impossible. Иначе выведите единственную строку из `N` символов M (мужское) и W (женское). Символ на `i`-й позиции соответствует статусу `i`-го места в той же нумерации, в которой они были перечислены во входных данных.

Пример ввода 1

2 2
2 1
1 2

Пример вывода 1

WW

Пример ввода 2

3 5
1 2
2 3
1 3
2 1
1 1

Пример вывода 2

WMWWM
Источник: Московская открытая олимпиада школьников по программированию, 2010/11 учебный год
loading