"Step right up!" cries the barker. "Step up to play a simple game of
arithmetic! Beat our man and we'll pay out five to two!"
You watch carnival patrons stepping up to try their hand at Fifteen. The
game is played on a long, thin table divided into nine sections marked
with the numerals 1 through 9. Behind the table stands a carnival worker,
called the dealer, who makes the first move of the game. The dealer
places a quarter (twenty-five cents) on a numeral of his choosing. Then the
patron puts a dime (ten cents) on some other numeral. Then it is the dealer's turn again, and moves proceed in alternation. With each move, one may only choose a numeral that hasn't been covered yet. The
object of the game is to use one's coins to cover three numerals that
add up to 15. It doesn't matter if a player has covered more than three
numerals, as long as exactly three of them sum to 15. The game ends
as soon as such a sum is formed, or, at the latest, once every numeral
has been covered. If the patron makes 15, he wins all the coins on the
table. Otherwise, the dealer keeps the money.
You've been watching for a while, and the dealer almost always wins. Regardless
of the five-to-two payout, the dealer has a
tremendous advantage. Not only does he get the first move, but he can win
by making 15 before the patron or merely by preventing the patron from
making 15. Then again, if the dealer always won, the supply of patrons
would quickly dry up. Sometimes the dealer makes a weak move that the
patron can exploit to win the game.
Given a record of the moves made so far, the dealer having made the
most recent move, determine whether the patron can win the game. The record is a int[] containing, in order of play, the numerals covered so far. The moves are guaranteed to be such that the game has not ended yet. If,
regardless of the patron's next move, the dealer wins by playing optimally
from this point on, return the String "LOSE" (quotes for clarity only). If there is
a way for the patron to win regardless of the dealer's moves, return a
String in the format "WIN X", where X is replaced by the
numeral the patron should cover next in order to win. If several moves
are equally promising, choose the one with the lowest numerical value.
|