Задача 3. Дворцовые перевороты
Имя входного файла — plots. in
Имя выходного файла — plots. out
Ограничение времени — 10 секунд на тест
Ограничение памяти — 16 Мb
Максимальная оценка за задачу — 34 балла
Имя входного файла — plots. in
Имя выходного файла — plots. out
Ограничение времени — 10 секунд на тест
Ограничение памяти — 16 Мb
Максимальная оценка за задачу — 34 балла.
(06.04.2002 14:07:50)
Дворцовые перевороты
Королевский двор состоит из N короля и других придворных, пронумерованных от 1 до N. Общее количество придворных N не превосходит 100. Придворные (включая короля) могут поддерживать друг с другом состоять в отношения (дружескиеличныех или служебныех отношения) отношениях, а могут и не поддерживать.. Дружеские и служебные отношения исключают друг друга. Между двумя придворными может поддерживаться не более одного отношения. Придворный не может находиться в дружеских или служебных отношениях сам с собой.
Личными отношениями являются дружба и вражда. Они исключают друг друга. ЛичныеДружеские отношения симметричны: если придворный А —- является другом В, то и B —-является другом А. У каждого придворного может быть не более K друзей. Вражеские отношения также симметричны: если А – враг B, то и B – враг А. Если два придворных являются друзьями одного придворного, но при этом непосредственно друзьями не являются, то они являются приятелями.
Придворный может сделать другом любого своего приятеля.
Придворный может поссориться с любым своим другом. Тогда они становятся врагами. Вражеские отношения также симметричны: если А – враг B, то и B – враг А. Число врагов у одного придворного не ограничено.
Служебные отношения асимметричны: один придворный —-– господин, ато другой –— его вассалслуга. У господина может быть несколько слуг, но слугаУ Господингосподина может иметь быть неограниченное число количество вассалов, но вассал может служить лишь одному господину. Слуга может быть господином других слуг. Назовем придворного независимым, если он не является ничьим слугойвассалом. Независимый придворный может стать вассалом любого другого придворного.
Дружеские и служебные отношения исключают друг друга. Если два придворных были друзьями (врагами), то после того, как один стал вассалом другого, они перестают быть друзьями (врагами). И наоборот, если вассалу и господину удается подружиться, то они перестают считаться вассалом и господином, а становятся просто друзьями.
Любой вассал может сделать другом любого другого
Среди придворных имеется интриган, который может совершать следующие действия: подружиться, поссориться, стать слугой вассалом, принудитьзаставить служить, устроить заговор.
ИнтриганПридворный может подружиться с любым другом своего другасделать другом любого друга своего друга, если при этом не нарушается ограничение на максимально разрешенноедопустимое количество друзей. Если слугавассалу и господину удается подружилисьиться, то они перестают бытьсчитаться вслугойассалом и господином, а становятся просто друзьями. Если интриган являетсяБудучи слугой, то он интриган Любой вассал может подружитьсясделать другом любого с любым другимого вассалслугойа, если при этом не нарушается ограничение на максимальное разрешенное допустимое количество друзей.
ПридворныйИнтриган может поссориться с любым своим другом. Тогда они перестают быть друзьями. становятся врагами.
Независимый Интриган, если он не является ничьим слугой, придворный может может стать слугойвассалом любого другого придворного. Если два придворных были друзьями, и один из них стал слугой другого, то они перестают быть друзьями.
Если два придворных были друзьями (врагами), то после того, как один стал вассалом другого, они перестают быть друзьями (врагами).
вассала.
Приобрести себе слуг вассаловслуг интриганпридворный может двумя способами: принуждением заставив служить или зустроив заговором. Действие «заставить служить»Принуждение заключается в том, что интриганпридворный делает своим слугойслугой вассалом независимого друга своего слугивассаласлуги. Действие «устроить зЗаговорзаговор» заключается в том, что интриган придворный делает своим вассаломслугойслугой своего придворноговрага, у которого есть друзья, причем всевсе они друзья которого являются и друзьями интриганапридворного. . Эти способы нельзя применить к придворному, который уже является чьим-либо слугой.
Действие «поссориться» приводит к разрушению имеющегося отношения дружбы, а другие действия заменяют старое отношение, если оно было, на новое.
Требуется разработать программу, которая составляет план дворцового переворотаплетущую интригиустраивающую дворцовый переворот в виде, то есть указывающую последовательностиь действий, позволяющейую (если возможно) придворному-интригану с номером N стать господином заданного придворного с номером 1короля, если такое возможно.
Входные данные
при условии, что остальные придворные пассивны и никаких действий не предпринимают.
Входные данные
В первой строке входного файла с именем plots. in записаныо через пробел общее числао придворных N (2 ≤ N ≤ 50). и K (1 ≤ K ≤ N -– 1) через пробел. В последующих строках файла записаны отношения придворных в следующем формате:
Отношение ПридворныйА ПридворныйВ
Здесь Отношение — один из символов:
Здесь Отношение – один из символов: Придворный1 Отношение Придворный2 | = > | = дружба, > господство (ПридворныйА —– господин, ПридворныйВ —– его слуга).где |
”x” – ( вражда), “>” – (господство (: Придворный1 – господин, Придворный2 – его слугавассал), “<”(услужение: Придворный1 – слуга, Придворный2 – его господин).
ПридворныйАорный1 и ПридворныйBорный2 —– номера придворных. Придворный номер 1 – это король, придворный номер N – тот самый интриган, который хочет стать господином короля. Отношение и номера придворных разделяются пробелами..Отношение и номера придворных разделяются пробелами.
Выходные данные
Интриган имеет номер N и интригует против придворного номер 1.
Выходные данные
Выходной файл с именем plots. out должен содержать последовательность действий интригана по одному действию в каждой строке в формате:
Действие Придворный
Здесь Действие — один из символов:
Здесь Действие – один из символов: | = x s > # | “=” – (подружиться), x поссориться, s стать слугой, > принудить, # устроить заговор. |
“x” – (поссориться), “<v” – (пойти в услужениестать вассалом), “>” – (принудить), “#” – (устроить заговор);
Придворный —– номер придворного, по отношению к которому совершается действие.
Интрига должна состоять не более чем из 100000 действий.
Действие и номер придворного разделяются пробелами.
Если успешная интрига при заданных входных данных невозможна, выходной файл должен содержать однуо строкулово со словом “ImpossibleNOTo solution”.
Интрига должна состоять не более чем из 100000 действий.
Пример 1
Входной файл plots. in | Выходной файл plots. out |
5 4 = 1 2 > 2 5 > 5 4 = 1 3 > 4 2 = 3 5 = 1 5 | x 1 = 2 # 1 |
Пример входного файла | Пример выходного файла для приведенного примера |
5 4 3 = 1 2 > = 21 = 52 > 5 4 = = 1 = 3 > 4 2 = 3 5= 3= 4 | = 1 = 2 x 1 # 1 |
Пример 2
Входной файл plots. in | Выходной файл plots. out |
5 2 = 1 2 > 2 5 > 5 4 = 1 3 = 3 5 | NOT |
Примечание
