Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Игра средней оплаты

(Время: 5 сек. Память: 64 Мб Сложность: 88%)

Игра средней оплаты – это игра для двух игроков, которая ведется на ориентированном графе. Вершины графа разделены на два множества: A и B. Первому игроку принадлежат вершины из множества A, а второму игроку – вершины из множества B. Каждая дуга uv графа помечена некоторым целым числом wuv.

Игра протекает следующим образом. Исходно специальная фишка помещается в выделенную вершину s графа. Затем игроки делают ходы, перемещая фишку по графу. Если фишка находится в вершине из множества A, то фишку перемещает первый игрок, а если в вершине из множества B, то второй игрок. Игроки поддерживают специальный счетчик z, в котором ведется суммирование чисел, записанных на дугах, по которым перемещается фишка. Исходно z = 0, после того как фишка перемещается по дуге uv, выполняется присваивание z = z + wuv. Игра продолжается до бесконечности.

Цель первого игрока – добиться, чтобы z → +∞ (иначе говоря, добиться, чтобы для любого числа x с некоторого момента игры z никогда не становился меньше чем x). Цель второго игрока – добиться, чтобы z → −∞. Если ни один из игроков не может добиться успеха, игра считается ничейной.

Например, рассмотрим игру, граф которой изображен на рисунке. Закрашенные вершины принадлежат первом игроку, а незакрашенные – второму. Исходно фишка располагается в вершине s.

Эта игра выигрышная для первого игрока. Он должен переместить фишку в вершину e а, второй игрок может либо перейти в положительный цикл f → g → f , из которого нет выхода, или переместить фишку в вершину c, из которой первый игрок переместит ее в b, и затем опять в e, добавляя +1 к z.

Можно показать, что если игра является выигрышной для одного из игроков, то у него существует детерминированная стратегия. Такая стратегия заключается в том, что для каждой вершины из тех, которые принадлежат игроку, указывается дуга, по которой следует перемещать фишку, если она оказалась в этой вершине. Стратегия не зависит ни от текущего значения z, ни от другой информации о предыдущем ходе игры.

Петя собирается поиграть в эту игру с Васей. Петя будет первым игроком, а Вася – вторым. Игроки выбрали граф для игры и стартовую вершину. Теперь Петя считает, что он выиграет в игре и выбрал себе выигрышную стратегию. Но он не до конца уверен. Он просит вас проверить: действительно ли выбранная им стратегия является выигрышной, то есть гарантирует, что z → +∞ вне зависимости от действий Васи.

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

Первая строка входного файла INPUT.TXT содержит два целых числа n и m – количество вершин и ребер в графе, соответственно. (1 ≤ n ≤ 2 000, 1 ≤ m ≤ 10 000). Вторая строка содержит n английских букв, которые описывают владельцев вершин, вершины, принадлежащие Пете, помечены как «A», а вершины, принадлежащие Васе – как «B». Третья строка содержит 0s – номер стартовой вершины.

Следующие m строк описывают дуги графа. Каждая дуга задается вершиной, в которой она начинается, вершиной, в которую она ведет, и числом, которым она помечена. Пометки дуг не превосходят 105 по абсолютной величине. Из каждой вершины исходит хотя бы одна дуга.

Последняя строка описывает стратегию Пети. Она содержит n целых чисел. Для каждой вершины задано либо число 0, если соответствующая вершина принадлежит Васе, либо номер дуги, по которой Петя собирается пойти, если фишка окажется в этой вершине. Дуги нумеруются с 1 в том порядке, в котором они заданы во входном файле.

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

В первой строке выходного файла OUTPUT.TXT выведите «Win», если стратегия Пети действительно является выигрышной. В противном случае следует вывести либо «Lose», если Вася может выиграть, либо «Draw», если Вася выиграть не может, но может свести игру к ничьей. В этих случаях на второй строке выведите Васину выигрышную, либо ничейную стратегию (против заданной Петиной) в том формате, в котором во входном файле задана стратегия Пети.

Примеры

INPUT.TXTOUTPUT.TXT
18 12
AAAABBBB
2
2 1 10
3 3 0
4 3 6
1 5 3
5 2 -13
2 6 -5
3 6 0
6 4 -5
6 7 -100
7 8 1
8 7 0
8 8 1
4 6 7 3 0 0 0 0
Win
28 12
AAAABBBB
2
2 1 10
3 3 0
4 3 6
1 5 3
5 2 -13
2 6 -5
3 6 0
6 4 -5
6 7 -100
7 8 1
8 7 0
8 8 1
4 1 7 3 0 0 0 0
Draw
0 0 0 0 5 8 10 11

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая командная олимпиада
 Вторая командная олимпиада
 Третья командная олимпиада
 Четвертая командная олимпиада
 Пятая командная олимпиада
 Шестая командная олимпиада
 Седьмая командная олимпиада
 A. Циклический сдвиг
 B. Произведение
 C. Пять делителей
 D. Игра средней оплаты
 E. Композиция
 F. Суровый садовник
 G. Задача о рюкзаке - 2
 H. Угадайка

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru