Зимние Олимпийские Игры. Соревнования по Крестикам-Ноликам на доске 3×3. В судейскую коллегию поступила недоигранная партия (у обоих участников выкачали слишком много крови на допинг-тесты). К моменту прерывания каждый из игроков сделал ровно по три хода. Судейская коллегия должна определить, как закончится партия при наилучшей игре обоих соперников.
Так как Крестиков поставлено ровно столько же, сколько и ноликов, то коллегия хотела присудить ничью, но тут Главный судья заметил, что одна из сторон угрожает выиграть партию одним ходом. Ваша задача — определить, какая из сторон выиграет при наилучшей игре каждого игрока. По международным правилам первый ход в партии делают Крестики, а победителем считается игрок, выставивший три своих символа в строке, столбце или диагонали.
Исходные данные
Дана таблица 3×3 из символов X, O (латинские заглавные буквы), отмечающих ходы соответственно крестиков и ноликов, и символов #, отмечающих незанятые пока поля.
Таблица содержит ровно три крестика и три нолика. Гарантируется, что партия не завершена, а именно, никакая строка, столбец и диагональ не заполнена целиком ни крестиками, ни ноликами.
Результат
В случае выигрыша Крестиков выведите «Crosses win», в случае выигрыша Ноликов — «Ouths win», в случае ничьей — «Draw».
Примеры
исходные данные | результат |
---|
XXO
#X#
#OO
| Ouths win
|
O#O
#X#
XOX
| Draw
|
XX#
XOO
#O# | Crosses win |
Автор задачи: Леонид Волков, Олег Кац
Источник задачи: V командное первенство школьников по программированию (2 марта 2002)