07/04/2025 07:40:05

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

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

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

WMWWM

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

25/06/2012	Лето 2012 - дорешивание ( 8G)
06/07/2012	Лето 2012 - 8 (G)
18/11/2014	Занятие 11 (B)