TheStringGame
SRM 428 · 2008-12-01 · by Vasyl[alphacom]
Problem Statement
John and Brus are playing a game where they alternate moves and John goes first. Initially, there is a string that contains only uppercase letters 'X', 'O' and 'L'. A move consists of replacing a single occurrence of 'X' with either 'O' or 'L'. After a player moves, if "LOL" (quotes for clarity) appears as a substring, that player immediately wins and the game ends. Otherwise, the game continues until there are no more 'X's left.
Both players use an optimal game strategy. If a player can win, he will follow the strategy that minimizes the number of moves in the game. Otherwise, if a player can make the game end without a winner, he will follow the strategy that does so (note that in this case the total number of moves in the game does not depend on the chosen strategy). Otherwise, if a player cannot win and cannot end the game in a draw, he will follow the strategy that maximizes the number of moves in the game.
You are given a String s containing the initial state of the game. If the game will end without a winner, return "Draw". If John will win the game, return "John x", and if Brus will win the game, return "Brus x", where x is the number of moves in the game, with no leading zeroes (all quotes for clarity).
Constraints
- s will contain between 1 and 16 characters, inclusive.
- Each character of s will be 'X', 'O' or 'L'.
- s will not contain "LOL" as a substring.
"XXOXXXLXLX" Returns: "John 1"
John can win by changing the 'X' between the two 'L's into a 'O'.
"LXXLXXL" Returns: "Brus 2"
Brus can win this game after John's first move, regardless of what John does.
"LLOOLLOOLLOOLLOO" Returns: "Draw"
No moves available.
"XXXXXXXXXXXXXXXX" Returns: "Brus 16"
"L" Returns: "Draw"
Submissions are judged against all 53 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TheStringGame with a public method string winner(string s) · 53 test cases · 2 s / 256 MB per case